实用标准 文档大全 /*一下总结一些二叉树的常见操作：包括建立二叉树 先/中/后序遍历二叉树 求二叉树的叶子节点个数 求二叉树的单分支节点个数 计算二叉树双分支节点个数 计算二叉树的高度 计算二叉树的所有叶子节点数*/ #include //c语言的头文件 #include//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) //如果节点为空，则返回0 return 0; else if((T->lchild==NULL) && (T->rchild==NULL))//否则如果节点左右孩子有一个为空，另一个存在，则返回1 return 1; else return(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; else return Sfenzhi(T->lchild )+Sfenzhi(T->rchild ); }

/*下面程序段计算二叉树的双分支节点个数*/ int Dfenzhi(Bitree T) { if(T==NULL) return 0;