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

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

2、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(); /地柜创

3、建右子树return T;/返回根节点/* 下面先序遍历二叉树*/*void preorder(Bitree T) / 先序遍历if(T)printf("%c-",T->data);preorder(T->lchild);preorder(T->rchild); */* 下面先序遍历二叉树非递归算法设计*/void preorder(Bitree T) /先序遍历非递归算法设计Bitree stMaxsize;/Bitree p;int top=-1; /栈置空if(T)定义循环队列存放节点的指针top+;sttop=T; /while(top>-1

4、)/根节点进栈栈不空时循环p=sttop; /栈顶指针出栈top-;printf("%c-",p->data );if(p->rchild !=NULL) /右孩子存在进栈top+;sttop=p->rchild ;if(p->lchild !=NULL) /左孩子存在进栈top+;sttop=p->lchild ;printf("n");/* 下面中序遍历二叉树*/*void inorder(Bitree T) /中序遍历if(T)inorder(T->lchild);printf("%c-",T

5、->data);inorder(T->rchild);*/* 下面中序遍历二叉树非递归算法设计*/void inorder(Bitree T) / 中序遍历Bitree stMaxsize; /Bitree p;int top=-1;if(T)定义循环队列，存放节点的指针p=T;while (top>-1|p!=NULL)/栈不空或者* 不空是循环while(p!=NULL)/扫描 *p的所有左孩子并进栈top+;sttop=p;p=p->lchild ;if(top>-1)p=sttop;/出栈 *p节点，它没有右孩子或右孩子已被访问。top-;printf(&

6、quot;%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 stMaxsize;Bitree p=T

7、,q;int flag;/int top=-1;/if(T)作为一个标志处理栈定时候用栈置空dowhile(p) /将*p 所在的左节点进栈top+;sttop=p;p=p->lchild ;q=NULL;flag=1; /设置 flag=1表示处理栈顶节点while(top!=-1&&flag=1)p=sttop;if(p->rchild=q)/右孩子不存在或者右孩子已被访问，访问之printf("%c-",p->data );top-;q=p;/让 q 指向刚被访问的节点elsep=p->rchild ; /p指向右孩子flag=

8、0;/设置 flag=0表示栈顶节点处理完毕while(top!=-1) ;/栈不空是循环printf("n");/* 下面层序遍历二叉树*/ /（层序遍历的模板）void levelorder(Bitree T) / 层序遍历二叉树Bitree p;Bitree quMaxsize; /int front, rear;/front=0;/定义一个循环队列定义队头队尾指针队列置空rear=0;rear+;/qurear=T;while(front!=rear)/根节点进队队列不空front=(front+1)%Maxsize;p=qufront;printf("%

9、C-",p->data );if(p->lchild !=NULL)/对头出队列访问对头节点左子树不空进队rear=(rear+1)%Maxsize;qurear=p->lchild ;if(p->rchild !=NULL)/右子树不空进队rear=(rear+1)%Maxsize;qurear=p->rchild ;/* 计算二叉树节点数*/* 方法一 */*int num(Bitree T)if(T=NULL)return 0;elsereturn num(T->lchild )+num(T->rchild )+1;*/* 方法二 */

10、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)/为空，另一个存在，则返回1否则如果节点左右孩子有一个return 1;elsereturn(countleaf(T->lchild)+countlea

11、f(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

12、->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 );/

13、* 计算二叉树的高度( 深度 */int depth (Bitree T)int lh,rh;if (T=NULL)return 0;elselh=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");preo

14、rder(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