二叉树排序算法.doc

实验报告课程名称：数据结构实验课程实验四、串的基本操作练习一、实验目的1. 掌握二叉树的存储实现 2. 掌握二叉树的遍历思想 3. 掌握二叉树的常见算法的程序实现二、实验环境VC+6.0三、实验内容1.输入字符序列，建立二叉树的二叉链表结构。（可以采用先序序列） 2.实现二叉树的先序、中序、后序的递归遍历算法。 3.实现二叉树的先序、中序、后序的非递归遍历算法。 4.求二叉树的高度。 5.求二叉树的结点个数。 6.求二叉树的叶子结点的个数。四、实验要求： 分别编写实现上述算法的子函数，并编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述子函数。五、实验步骤和结果1.打开vc，新建文本，命名二叉树算法，编写代码。2.编写代码：#include #include #define STACK_INIT_SIZE 100#define STACKINCREMENT 10int i=0;/*-建立堆栈-*/typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;/树类型typedef struct SqStack BiTNode *base; BiTNode *top; int stacksize; SqStack;/栈类型void InitStack(SqStack *S)/创建二叉树 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(BiTNode); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *(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; else return 0;/*-递归部分-*/BiTree Create(BiTree T)/建立二叉树 char ch; ch=getchar(); if(ch=#) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) printf(申请内存空间失败!); T-data=ch; T-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-lchild)+Sumleaf(T-rchild);*/int PreOrder_1(BiTree T)/先序递归 if(T) printf(%c,T-data);/根节点i+; PreOrder_1(T-lchild); PreOrder_1(T-rchild); return i; void InOrder_1(BiTree T)/中序递归 if(T) InOrder_1(T-lchild); printf(%c,T-data);/根节点 InOrder_1(T-rchild); void PostOrder_1(BiTree T)/后序递归 if(T) PostOrder_1(T-lchild); PostOrder_1(T-rchild); printf(%c,T-data);/根节点 int Depth(BiTree T)/计算高度 int dep=0,depl,depr; if(!T) dep=0; else depl=Depth(T-lchild); depr=Depth(T-rchild); dep=1+(depldepr?depl:depr); return dep; /*-非递归部分-*/void 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) 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); p=p-lchild; else p=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) do while(p-lchild|p-rchild)&marktop+1!=2)/循环 直到让p向左滑到叶子节点 top+; Push(&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;/访问右子树 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); PostOrder_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(nn); 六、实验结果和讨论1.首先，代码，修改语法错误，调试。运行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.程序运算复杂，代码长度大，调试困难，漏洞多，尤其是后序非递归的遍历，用到