二叉树的建立与先序中序后序遍历-求叶子节点个数-求分支节点个数-求二叉树的高度

/*一下总结一些二叉树的常见操作：包括建立二叉树先/中/后序遍历二叉树求二叉树的叶子节点个数求二叉树的单分支节点个数计算二叉树双分支节点个数计算二叉树的高度计算二叉树的所有叶子节点数*/#includestdio.h//c语言的头文件#includestdlib.h//c语言的头文件stdlib.h千万别写错了#defineMaxsize100/*创建二叉树的节点*/typedefstructBTNode//结构体struct是关键字不能省略结构体名字可以省略（为无名结构体）//成员类型可以是基本型或者构造形，最后的为结构体变量。{chardata;structBTNode*lchild,*rchild;}*Bitree;/*使用先序建立二叉树*/BitreeCreatetree()//树的建立{charch;BitreeT;ch=getchar();//输入一个二叉树数据if(ch=='')//''中间有一个空格的。T=NULL;else{T=(Bitree)malloc(sizeof(Bitree));//生成二叉树(分配类型*)malloc(分配元素个数*sizeof(分配类型))T-data=ch;T-lchild=Createtree();//递归创建左子树T-rchild=Createtree();//地柜创建右子树}returnT;//返回根节点}/*下面先序遍历二叉树*//*voidpreorder(BitreeT)//先序遍历{if(T){printf(%c-,T-data);preorder(T-lchild);preorder(T-rchild);}}*//*下面先序遍历二叉树非递归算法设计*/voidpreorder(BitreeT)//先序遍历非递归算法设计{Bitreest[Maxsize];//定义循环队列存放节点的指针Bitreep;inttop=-1;//栈置空if(T){top++;st[top]=T;//根节点进栈while(top-1)//栈不空时循环{p=st[top];//栈顶指针出栈top--;printf(%c-,p-data);if(p-rchild!=NULL)//右孩子存在进栈{top++;st[top]=p-rchild;}if(p-lchild!=NULL)//左孩子存在进栈{top++;st[top]=p-lchild;}}printf(\n);}}/*下面中序遍历二叉树*//*voidinorder(BitreeT)//中序遍历{if(T){inorder(T-lchild);printf(%c-,T-data);inorder(T-rchild);}}*//*下面中序遍历二叉树非递归算法设计*/voidinorder(BitreeT)//中序遍历{Bitreest[Maxsize];//定义循环队列，存放节点的指针Bitreep;inttop=-1;if(T){p=T;while(top-1||p!=NULL)//栈不空或者*不空是循环{while(p!=NULL)//扫描*p的所有左孩子并进栈{top++;st[top]=p;p=p-lchild;}if(top-1){p=st[top];//出栈*p节点，它没有右孩子或右孩子已被访问。top--;printf(%c-,p-data);//访问p=p-rchild;//扫描*p的右孩子节点}}printf(\n);}}/*下面后序遍历二叉树*//*voidpostorder(BitreeT)//后序遍历{if(T){postorder(T-lchild);postorder(T-rchild);printf(%c-,T-data);}}*//*二叉树后序遍历非递归算法设计*/voidpostorder(BitreeT)//后序遍历非递归{Bitreest[Maxsize];Bitreep=T,q;intflag;//作为一个标志处理栈定时候用inttop=-1;//栈置空if(T){do{while(p)//将*p所在的左节点进栈{top++;st[top]=p;p=p-lchild;}q=NULL;flag=1;//设置flag=1表示处理栈顶节点while(top!=-1&&flag==1){p=st[top];if(p-rchild==q)//右孩子不存在或者右孩子已被访问，访问之{printf(%c-,p-data);top--;q=p;//让q指向刚被访问的节点}else{p=p-rchild;//p指向右孩子flag=0;//设置flag=0表示栈顶节点处理完毕}}}while(top!=-1);//栈不空是循环printf(\n);}}/*下面层序遍历二叉树*///（层序遍历的模板）voidlevelorder(BitreeT)//层序遍历二叉树{Bitreep;Bitreequ[Maxsize];//定义一个循环队列intfront,rear;//定义队头队尾指针front=0;//队列置空rear=0;rear++;//根节点进队qu[rear]=T;while(front!=rear)//队列不空{front=(front+1)%Maxsize;//对头出队列p=qu[front];printf(%C-,p-data);//访问对头节点if(p-lchild!=NULL)//左子树不空进队{rear=(rear+1)%Maxsize;qu[rear]=p-lchild;}if(p-rchild!=NULL)//右子树不空进队{rear=(rear+1)%Maxsize;qu[rear]=p-rchild;}}}/*计算二叉树节点数*//*方法一*//*intnum(BitreeT){if(T==NULL)return0;else{returnnum(T-lchild)+num(T-rchild)+1;}}*//*方法二*/intnum(BitreeT){if(T!=NULL)returnnum(T-lchild)+num(T-rchild)+1;return0;}/*下面程序段计算二叉树的叶子节点个数*/intcountleaf(BitreeT){if(T==NULL)//如果节点为空，则返回0return0;elseif((T-lchild==NULL)&&(T-rchild==NULL))//否则如果节点左右孩子有一个为空，另一个存在，则返回1return1;elsereturn(countleaf(T-lchild)+countleaf(T-rchild));//否则返回左右子树叶子节点之和}/*下面程序段计算二叉树的单分支节点个数*/intSfenzhi(BitreeT){if(T==NULL)return0;elseif(T-lchild==NULL&&T-rchild!=NULL||T-lchild!=NULL&&T-rchild==NULL)//为单分支节点returnSfenzhi(T-lchild)+Sfenzhi(T-rchild)+1;elsereturnSfenzhi(T-lchild)+Sfenzhi(T-rchild);}/*下面程序段计算二叉树的双分支节点个数*/intDfenzhi(BitreeT){if(T==NULL)return0;elseif(T-lchild!=NULL&&T-rchild!=NULL||T-lchild!=NULL&&T-rchild!=NULL)//为单分支节点returnDfenzhi(T-lchild)+Dfenzhi(T-rchild)+1;elsereturnDfenzhi(T-lchild)+Dfenzhi(T-rchild);}/*计算二叉树的高度(深度*/intdepth(BitreeT){intlh,rh;if(T==NULL)return0;else{lh=depth(T-lchild);//递归左子树rh=depth(T-rchild);//递归右子树return(lhrh)?(lh+1):(rh+1);//高度等于左子树和右子树中大者加1}}/*下面为主函数*/voidmain(){BitreeT;printf(先序创建二叉树,用空格代表虚结点：\n);T=Createtree();printf(先序遍历：\n);preorder(T);printf(\n);printf(中序遍历：\n);inorder(T);printf(\n);printf(后序遍历：\n);postorder(T);printf(\n);printf(层序遍历：\n);levelorder(T);printf(\n);printf(二叉树的节点数为:);printf(%d个,num(T));printf(\n);printf(二叉树的叶子节点数为:);printf(%d个,countleaf(T));printf(\n);printf(二叉树的单分支节点数为:);printf(%d个,Sfenzhi(T));printf(\n);printf(二叉树的双分支节点数为:);printf(%d个,Dfenzhi(T));printf(\n);printf(二叉树的高度（深度）为:);printf(%d,depth(T));printf(\n);}