二叉树应用示例

1、（1）根据输入字符序列，建立二叉链表；（2）用递归算法实现输出二叉树的前序、中序、后序遍历序列；（3）用非递归算法实现输出二叉树的前序、中序遍历序列；（4）求二叉树的叶子个数；（5）求度为1 的结点的个数；（6）求二叉树的高度。建立二叉链表的方法有多种，前面已经介绍了一种，即将二叉树扩充成完全二叉树后 带虚点一起将结点按层次次序排列，然后依次输入该序列中各结点，创建二叉链表。在下面 程序中使用的是另外一种建立二叉链表的方法，其主要的实现思想是：添加虚结点，将二叉 树中的每一个结点都扩充成度为2 的结点，然后对扩充后的二叉树按前序遍历得到前序序 列，依次输入序列中各结点，建立二叉链表。例如：若要

2、创建5.13 的二叉树对应的二叉链 表，应该依次输入ABC#FG#D#E# （其中#表示虚点）。这是一个利用递归特性实现创建 二叉链表的算法，C函数为下面程序中的createBiTree （）。完整程序如下：#include stdio.h#include malloc.h#define MAXSIZE 100typedef char DataType;typedef struct Node/* 二叉链表存储结构 */ DataType data;struct Node *lchild,*rchild;BiTree;typedef BiTree* SElemType ;/* 栈中数据元素类型，

3、栈中保存结点指针 */typedef struct SElemType dataMAXSIZE;int top;SeqStack;/* 栈的类型定义，顺序栈 */* 栈的基本操作的实现 */*初始化栈/*初始化栈*/*首先建立栈空间，然后初始化栈顶指针*/ SeqStack *s;s=(SeqStack*)malloc(sizeof(SeqStack);s-top= -1;return s;int push (SeqStack *s, SElemType x) if (s-top=MAXSIZE-1)/*栈满不能入栈*/ printf(overflow); return 0;s-top+; s

4、-datas-top=x;return 1;void pop (SeqStack *s)/*出栈，假设栈不空*/ s-top-;int empty (SeqStack *s) if (s-top= -1) return 1;else return 0;SElemType top (SeqStack *s)/*设栈不空*/ return (s-datas-top );/* 二叉链表的基本操作的实现 */BiTree* createBiTree () /* 创建二叉链表递归算法 */ DataType ch;BiTree * T; ch=getchar();if(ch=#) return NULL

5、;else T=(BiTree *)malloc(sizeof(BiTree); T-data=ch;T-lchild=createBiTree();T-rchild=createBiTree(); return T;void PreOrder(BiTree *T) /* 前序遍历二叉树的递归算法 */ if(T) printf(%c,T-data); PreOrder(T-lchild); PreOrder(T-rchild);void InOrder(BiTree * T) /* 中序遍历二叉树的递归算法 */ if(T) InOrder (T-lchild); printf(%c,T-d

6、ata); InOrder (T-rchild);void PostOrder (BiTree * T)/* 后序遍历二叉树的递归算法*/ if(T) PostOrder (T-lchild); PostOrder (T-rchild); printf(%c,T-data);void PreOrderFei(BiTree *p) /* 前序遍历二叉树的非递归算法 */ SeqStack *s;s=initSeqStack();while(1) while(p) printf(%c, p-data); push(s,p); p=p-lchild; /*先访问结点，后压栈 */ if (empty

7、(s) break;p=top(s); pop(s); p=p-rchild;void InOrderFei(BiTree *p) /* 中序遍历二叉树的非递归算法 */ SeqStack *s;s=initSeqStack();while(1) while(p) push(s,p); p=p-lchild;/*先将结点指针压栈，待出栈时再访问 */if (empty(s) break;p=top(s); pop(s); printf(%c, p-data); p=p-rchild;int oneChild(BiTree *T) /* 求度为1 的结点数递归实现 */ int num=0,nu

8、m1,num2;if(T=NULL) return 0;else if(T-lchild=NULL & T-rchild!=NULL|T-lchild!=NULL &T-rchild=NULL) num=l;/*若当前访问结点的度为1,则num=1，否则为0*/numl=oneChild(T-lchild); /*num1 为左子树中度为 1 的结点数*/ num2=oneChild(T-rchild ); /*num2 为右子树中度为 1 的结点数*/ return num+num1+num2;int leafs(BiTree *T)/* 求叶子结点数 */ int num1,num2;if

9、(T=NULL) return 0;else if(T-lchild=NULL &T-rchild =NULL) return 1;num1=leafs(T-lchild );/*求左子树中叶子结点数*/num2=leafs(T-rchild );/*求右子树中叶子结点数*/return num1+num2;int height(BiTree *T)/* 求树高 */ int i,j;if(!T) return 0;i=height(T-lchild);/* 求左子树的高度*/ j=height(T-rchild);/*求右子树的高度*/return ij?i+1:j+1;/*二叉树的高度为左

10、右子树中较高的高度加 1*/ void main() BiTree *root; root=NULL;printf(nnt请输入结点的前序序列创建二叉树：#表示空：”)； root=createBiTree();/* 生成二叉树 */ printf(nt前序遍历二叉树-递归：n);PreOrder(root)；printf(nt前序遍历二叉树-非递归：n); PreOrderFei(root);printf(nt中序遍历二叉树-递归：n); InOrder(root);printf(nt中序遍历二叉树-非递归：n); InOrderFei(root);printf(nt后序遍历二叉树-递归：n); PostOrder(root);printf(nt 二叉树中叶子结点数为：%d, leafs(root);printf(nt 二叉树中度为 1 的结点数为：%d, oneChild(root);printf(nt 二叉树的高度为：d,height(root); getchar();运行