程序二叉树排序算法.docx
《程序二叉树排序算法.docx》由会员分享，可在线阅读，更多相关《程序二叉树排序算法.docx（15页珍藏版）》请在冰点文库上搜索。
程序二叉树排序算法
实验报告
课程名称：
数据结构实验课程
实验四、串的基本操作练习
一、实验目的
1.掌握二叉树的存储实现
2.掌握二叉树的遍历思想
3.掌握二叉树的常见算法的程序实现
二、实验环境
VC++6.0
三、实验内容
1.输入字符序列，建立二叉树的二叉链表结构。
（可以采用先序序列）
2.实现二叉树的先序、中序、后序的递归遍历算法。
3.实现二叉树的先序、中序、后序的非递归遍历算法。
4.求二叉树的高度。
5.求二叉树的结点个数。
6.求二叉树的叶子结点的个数。
四、实验要求：
分别编写实现上述算法的子函数，并编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述子函数。
五、实验步骤和结果
1.打开vc，新建文本，命名二叉树算法，编写代码。
2.编写代码：
#include
#include
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
inti=0;
/*--------------------------------------建立堆栈------------------------------------------*/
typedefstructBiTNode
{
chardata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;//树类型
typedefstructSqStack
{
BiTNode*base;
BiTNode*top;
intstacksize;
}SqStack;//栈类型
voidInitStack（SqStack*S）//创建二叉树
{
S->base=（BiTNode*）malloc（STACK_INIT_SIZE*sizeof（BiTNode））;
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
voidPush（SqStack*S,BiTNodee）//进栈
{
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++;
}
BiTNodePop（SqStack*S）//出栈
{
S->top--;
return*S->top;
}
intStackEmpty（SqStack*S）//判断栈是否非空
{
if（S->top==S->base）
return1;
else
return0;
}
/*---------------------------------------------递归部分-------------------------------------------*/
BiTreeCreate（BiTreeT）//建立二叉树
{
charch;
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）;
}
returnT;
}
intSumleaf（BiTreeT）//计算叶子节点
{
intsum=0,m,n;
if（T）
{
if（（!
T->lchild）&&（!
T->rchild））
sum++;
m=Sumleaf（T->lchild）;
sum+=m;
n=Sumleaf（T->rchild）;
sum+=n;
}
returnsum;
}
/*intSumleaf（BiTreeT）//老师课堂上的计算叶子数的代码，没有问题
{
if（!
（T->lchild&&T->rchild））
return1;
else
return（Sumleaf（T->lchild）+Sumleaf（T->rchild））;
}*/
intPreOrder_1（BiTreeT）//先序递归
{
if（T）
{
printf（"%c",T->data）;//根节点
i++;
PreOrder_1（T->lchild）;
PreOrder_1（T->rchild）;
}
returni;
}
voidInOrder_1（BiTreeT）//中序递归
{
if（T）
{
InOrder_1（T->lchild）;
printf（"%c",T->data）;//根节点
InOrder_1（T->rchild）;
}
}
voidPostOrder_1（BiTreeT）//后序递归
{
if（T）
{
PostOrder_1（T->lchild）;
PostOrder_1（T->rchild）;
printf（"%c",T->data）;//根节点
}
}
intDepth（BiTreeT）//计算高度
{
intdep=0,depl,depr;
if（!
T）
dep=0;
else
{
depl=Depth（T->lchild）;
depr=Depth（T->rchild）;
dep=1+（depl>depr?
depl:
depr）;
}
returndep;
}
/*-------------------------------------非递归部分----------------------------------------*/
voidPreOrder_2（BiTreeT）//先序非递归
{
SqStackS;
BiTreep=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）;
}
}
voidInOrder_2（BiTreeT）//中序非递归
{
SqStackS;
BiTreep,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;
}
}
}
voidPostOrder_2（BiTreeT）//后序非递归
{
intmark[100];//标示
intt=0;
inttop=-1;//下标
SqStackS;
BiTreep=T,q;
InitStack（&S）;
q=（BiTNode*）malloc（sizeof（BiTNode））;
if（p&&（p->lchild||p->rchild））
{
do
{
while（（p->lchild||p->rchild）&&mark[top+1]!
=2）//循环直到让p向左滑到叶子节点
{
top++;
Push（&S,*p）;//每循环一次，当前结点入栈
mark[top]=1;//结点第一次入栈时，标志为1
if（p->lchild）
p=p->lchild;//找最左子树
else
if（p->rchild）
p=p->rchild;
}
if（p）
printf（"%c",p->data）;
p=q;
*p=Pop（&S）;
top--;//出栈，下标归位
if（!
p->rchild||!
p->lchild）//防止出现不必要的再次入栈
mark[top+1]=2;
if（mark[top+1]==1&&p->rchild）//若结点是第一次出栈，则再入栈
{
top++;
Push（&S,*p）;
mark[top]=2;//结点第二次入栈时，标志为2
p=p->rchild;//访问右子树
mark[top+1]=0;
}
if（mark[0]==2&&t==0）//当栈剩下最后一个结点的时候，把下标初始化。
{
inti;
t++;
for（i=0;i<100;i++）
{
mark[i]=0;
}
}
}while（top!
=-1&&!
StackEmpty（&S）&&p）;
printf（"%c",p->data）;//输出根节点
}
else
if（p）
printf（"%c",p->data）;//当树仅有一个结点时
}
voidmain（）
{
BiTreeTa;
intsum,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高度为:
%d\n",dep）;
printf（"***********************非递归遍历**************************"）;
printf（"\n非递归先序遍历:
\n"）;
PreOrder_2（Ta）;
printf（"\n非递归中序遍历:
\n"）;
InOrder_2（Ta）;
printf（"\n非递归后序遍历:
\n"）;
PostOrder_2（Ta）;
printf（"\n\n"）;
}
六、实验结果和讨论
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.程序运算复杂，代码长度大，调试困难，漏洞多，尤其是后序非递归的遍历，用到了二次进栈，并对进栈的次数进行标记，中间会有很多比较特殊的二叉树会使程序无法完全访问到二叉树的各个结点，造成逻辑错误，做了多次的修改，完善，以上输入了几种有代表性的树，都是本来不能运行成功，修改后正常运行的结果。
3.遇到一个难题，就是不知道如何提示用户输入的字符是否能构成一棵完整的二叉树。
4.代码很长，可能对一些较为特殊的二叉树的处理会出错，目前试过好几种有代表性的树，均未发现问题。
考虑到时间问题，没作深入的探讨。
升级会员 