/*一下总结一些二叉树的常见操作：包括建立二叉树先/中/后序遍历二叉树求二叉树的叶子节点个数求二叉树的单分支节点个数计算二叉树双分支节点个数计算二叉树的高度计算二叉树的所有叶子节点数*/#include<stdio.h> //c语言的头文件#include<stdlib.h>//c语言的头文件stdlib.h千万别写错了#define Maxsize 100/*创建二叉树的节点*/typedef struct BTNode //结构体struct 是关键字不能省略结构体名字可以省略（为无名结构体）//成员类型可以是基本型或者构造形，最后的为结构体变量。

{char data;struct BTNode *lchild,*rchild;}*Bitree;/*使用先序建立二叉树*/Bitree Createtree() //树的建立{char ch;Bitree T;ch=getchar(); //输入一个二叉树数据if(ch==' ') //' '中间有一个空格的。

T=NULL;else{ T=(Bitree)malloc(sizeof(Bitree)); //生成二叉树(分配类型*)malloc(分配元素个数*sizeof(分配类型))T->data=ch;T->lchild=Createtree(); //递归创建左子树T->rchild=Createtree(); //地柜创建右子树}return T;//返回根节点}/*下面先序遍历二叉树*//*void preorder(Bitree T) //先序遍历{if(T){printf("%c-",T->data);preorder(T->lchild);preorder(T->rchild);}} *//*下面先序遍历二叉树非递归算法设计*/void preorder(Bitree T) //先序遍历非递归算法设计{Bitree st[Maxsize];//定义循环队列存放节点的指针Bitree p;int top=-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");}}/*下面中序遍历二叉树*//*void inorder(Bitree T) //中序遍历{if(T){inorder(T->lchild);printf("%c-",T->data);inorder(T->rchild);}}*//*下面中序遍历二叉树非递归算法设计*/void inorder(Bitree T) //中序遍历{Bitree st[Maxsize]; //定义循环队列，存放节点的指针Bitree p;int top=-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");}}/*下面后序遍历二叉树*//*void postorder(Bitree T) //后序遍历{if(T){postorder(T->lchild);postorder(T->rchild);printf("%c-",T->data);}}*//*二叉树后序遍历非递归算法设计*/void postorder(Bitree T) //后序遍历非递归{Bitree st[Maxsize];Bitree p=T,q;int flag; //作为一个标志处理栈定时候用int top=-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");}}/*下面层序遍历二叉树*/ //（层序遍历的模板）void levelorder(Bitree T) //层序遍历二叉树{Bitree p;Bitree qu[Maxsize]; //定义一个循环队列int front, 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 ;}}}/*计算二叉树节点数*//*方法一*//*int num(Bitree T){if(T==NULL)return 0;else{return num(T->lchild )+num(T->rchild )+1;}}*//*方法二*/int num (Bitree T)if(T!=NULL)return num(T->lchild )+num(T->rchild )+1;return 0;}/*下面程序段计算二叉树的叶子节点个数*/int countleaf(Bitree T){if(T==NULL) //如果节点为空，则返回0return 0;else if((T->lchild==NULL) && (T->rchild==NULL))//否则如果节点左右孩子有一个为空，另一个存在，则返回1return 1;elsereturn(countleaf(T->lchild)+countleaf(T->rchild));//否则返回左右子树叶子节点之和}/*下面程序段计算二叉树的单分支节点个数*/int Sfenzhi(Bitree T){if(T==NULL)return 0;else if (T->lchild==NULL&&T->rchild!=NULL||T->lchild!=NULL&&T->rchild==NULL) //为单分支节点return Sfenzhi(T->lchild )+Sfenzhi(T->rchild )+1;elsereturn Sfenzhi(T->lchild )+Sfenzhi(T->rchild );}/*下面程序段计算二叉树的双分支节点个数*/int Dfenzhi(Bitree T){if(T==NULL)return 0;else if (T->lchild!=NULL&&T->rchild!=NULL||T->lchild!=NULL&&T->rchild!=NULL) //为单分支节点return Dfenzhi(T->lchild )+Dfenzhi(T->rchild )+1;elsereturn Dfenzhi(T->lchild )+Dfenzhi(T->rchild );}/*计算二叉树的高度(深度*/int depth (Bitree T){int lh,rh;if (T==NULL)return 0;else{lh=depth(T->lchild); //递归左子树rh=depth(T->rchild); //递归右子树return (lh>rh)?(lh+1):(rh+1); //高度等于左子树和右子树中大者加1 }}/*下面为主函数*/void main(){Bitree T;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");}。