《二叉树排序算法.docx》由会员分享，可在线阅读，更多相关《二叉树排序算法.docx（12页珍藏版）》请在三一办公上搜索。
1、实验报告课程名称：数据结构实验课程 实验四、串的基本操作练习一、实验目的1, 掌握二叉树的存储实现2, 掌握二叉树的遍历思想3, 掌握二叉树的常见算法的程序实现二、实验环境VC+6.0三、实验内容1. 输入字符序列，建立二叉树的二叉链表结构。（可以采用先序序列）2. 实现二叉树的先序、中序、后序的递归遍历算法。3. 实现二叉树的先序、中序、后序的非递归遍历算法。4. 求二叉树的高度。5. 求二叉树的结点个数。6. 求二叉树的叶子结点的个数。四、实验要求：分别编写实现上述算法的子函数，并编写一个主函数，在主函数中设计一个 简单的菜单，分别调用上述子函数。五、实验步骤和结果1. 打开vc，新建文本
2、，命名二叉树算法，编写代码。2. 编写代码：#include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10int i=0;/*建立堆栈*/typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;/树类型typedef struct SqStackBiTNode *base;BiTNode *top;int stacksize; SqStack;/ 栈类型void InitStack(SqStack *S)/ 创建二
3、叉树S-base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode);S-top=S-base;S-stacksize=STACK_INIT_SIZE;void Push(SqStack *S,BiTNode e)/ 进栈if(S-top - S-base = S-stacksize)/如 果栈空间不足S-base=(BiTNode*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(B iTNode);S-top=S-base+S-stacksize;S-stacksize+=STACKINCR
4、EMENT;*(S-top)=e;S-top+;BiTNode Pop(SqStack *S)/ 出栈S-top -;return *S-top;int StackEmpty(SqStack *S)/ 判断栈是否非空if(S-top = S-base )return 1;elsereturn 0;/* 递 归 部 分*/BiTree Create(BiTree T)/健立二叉树char ch;ch=getchar();if(ch=#)T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)printf(-申请内存空间失败!)；T-data=ch;T
5、-lchild=Create(T-lchild);T-rchild=Create(T-rchild);return T;int Sumleaf(BiTree T)/计算叶子节点int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)sum+;m=Sumleaf(T-lchild);sum+=m;n=Sumleaf(T-rchild);sum+=n;return sum;/*int Sumleaf(BiTree T)/老师课堂上的计算叶子数的代码，没有问题 if(!(T-lchild&T-rchild)return 1;elsereturn(Sumleaf(T-l
6、child)+Sumleaf(T-rchild);*/int PreOrder_1(BiTree T)/先 序递归if(T)p r5if=%c LTvd a足4!nr +preordell(Tvch=d)J preordell?vrch=d)J) Irer+urn Lvoid - n orderly BHree T- Im)-nordell(Tv-ch=d)Jp r5if=%c LTvd a足4!nr -nordell?vrchi-d)J) Ivoid pos6rdell(B=iree T5ffiffi Im)pos6rderl(Tvch=d)j pos6rdell(Tvrch=d)j p r
7、5if=%c LTvd a足4!nr5i Depih(B=iree Ty/i+wwwini depgdepLdeprjm_T)depn。e-sedepllDepih(Tvch=d)J deprnDepih(Tvrch=d)J depnl+depvdeprpdeprTdepr)； return dep;/*箱鸨8void PreOrder_2(BiTree T)/先 序非递归(一SqStack S;BiTree p=T,q;q=(BiTNode *)malloc(sizeof(BiTNode);InitStack(&S);if(p)Push(&S,*p);while(!StackEmpty(&S
8、)p=q;*p=Pop(&S);/移到叶子时，出栈，输出出栈元素printf(%c,p-data);if(p-rchild)/如果有右孩子，访问右孩子，并沿右孩子移位Push(&S,*p-rchild);if(p-lchild)/如果没有右孩子，访问左孩子，并移到左孩子Push(&S,*p-lchild);void InOrder_2(BiTree T)/ 中序非递归SqStack S;BiTree p,q;p=T;InitStack(&S);q=(BiTNode *)malloc(sizeof(BiTNode);while(p|!StackEmpty(&S)if(p)Push(&S,*p);
9、p=p-lchild;elsep=q;*p=Pop(&S);printf(%c,p-data);p=p-rchild;void PostOrder_2(BiTree T)/后 序非递归(一 _int mark100;/ 标示int t=0;int top=-1;/ 下标SqStack S;BiTree p=T,q;InitStack(&S);q=(BiTNode *)malloc(sizeof(BiTNode);if(p&(p-lchild|p-rchild)dowhile(p-lchild|p-rchild)&marktop+1!=2)/循环 直到让 p 向左 滑到叶子节点top+;Push
10、(&S,*p);/每循环一次，当前结点入栈 marktop=1;/结点第一次入栈时，标志为1 if(p-lchild)p=p-lchild;/找最左子树elseif(p-rchild)p=p-rchild;if(p)printf(%c,p-data);p=q;*p=Pop(&S);top-;/出栈，下标归位if(!p-rchild|!p-lchild)/防止出现不必要的再次入栈 marktop+1=2;if(marktop+1=1&p-rchild)/若结点是第一次出栈，则再入栈top+;Push(&S,*p);marktop=2;/结点第二次入栈时，标志为2 p=p-rchild;/访问右子
11、树marktop+1=0;if(mark0=2&t=0)/当栈剩下最后一个结点的时候，把下标初始 化。int i;t+;for(i=0;idata);/ 输出根节点elseif(p)printf(%c,p-data);/当树仅有一个结点时 void main() BiTree Ta;int sum,dep,total;printf(输入数据创建二叉树”)；Ta=Create(Ta);printf(*);printf(n递归先序遍历:n);total=PreOrder_1(Ta);printf(n递归中序遍历:n);InOrder_1(Ta);printf(n递归后序遍历:n);PostOrde
12、r_1(Ta);sum=Sumleaf(Ta);printf(n);printf(* 结点总数叶子数*);printf(n该二叉树结点总数为:d”,total);printf(n 叶子总数为:d”,sum);dep=Depth(Ta);printf(n 高度为:dn”,dep);printf(* 非 递 归*);printf(n非递归先序遍历:n);PreOrder_2(Ta);printf(n非递归中序遍历:n);InOrder_2(Ta);printf(n非递归后序遍历:n);PostOrder_2(Ta);printf(nnH);六、实验结果和讨论1.首先，代码，修改语法错误，调试。运行
13、2.按要求输入二叉树abc#de#g#f#3.运行结果符合要求，再次输入一颗二叉树。-+a#*b#-c#d#/e#f#4.运算结果合格，再次输入。abcd#e#fg#h#ijl#m#kn#o#5.运行结果正确。下面输入特殊的树，进行健壮性检查，比如输入空树，#6.空树没有结点叶子，结点总数和高度都为0,其他的运算均不输出任何东西 再输入仅有一个结点的树a#。七、总结1. 通过本实验了解了二叉树的遍历算法，复习了递归，堆栈的使用。2. 程序运算复杂，代码长度大，调试困难，漏洞多，尤其是后序非递归的遍历， 用到了二次进栈，并对进栈的次数进行标记，中间会有很多比较特殊的二叉树 会使程序无法完全访问到二叉树的各个结点，造成逻辑错误，做了多次的修改， 完善，以上输入了几种有代表性的树，都是本来不能运行成功，修改后正常运 行的结果。3. 遇到一个难题，就是不知道如何提示用户输入的字符是否能构成一棵完整的二 叉树。4. 代码很长，可能对一些较为特殊的二叉树的处理会出错，目前试过好几种有代 表性的树，均未发现问题。考虑到时间问题，没作深入的探讨。
