&nbsh1; 欢迎阅读本文档,希望本文档能对您有所帮助!
二叉树的遍历学习心得
目录
一设计思想..........................................21递归遍历二叉树算法思想:.......................................22非递归遍历二叉树算法思想:.....................................2
二算法
图........................................4三源代码............................................4四运行结果.........................................16五遇到的问
及解决.................................161遇到的问题:..................................................162解决
:....................................................16六心得体会.........................................17
1
一设计思想
1递归遍历二叉树算法思想:
(1)先序遍历:首先判断根结点是否为空,为空则停止遍历,不为空则将左子作为新的根结点重新进行上述判断,左子遍历结束后,再将右子作为根结点判断,直至结束。到达每一个结点时,打印该结点数据,即得先序遍历结果。若二叉树非空,则依次进行如下操作:(1)访问跟结点;(2)前序遍历左子树;(3)前序遍历右子树。
(2)中序遍历:首先判断根结点是否为空,为空则结束,不为空则将左子作为根结点再进行判断,打印左子,然后打印二叉树的根结点,最后再将右子作为参数进行判断,打印右子,直至结束。若二叉树非空,则依次进行如下操作:(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。
(3)后序遍历:指针到达一个结点时,判断该结点是否为空,为空则停止遍历,不为空则将左子作为新的结点参数进行判断,打印左子。左子判断完成后,将右子作为结点参数传入判断,打印右子。左右子判断完成后打印根结点。若二叉树非空,则依次进行如下操作:(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。
2非递归遍历二叉树算法思想:
(4)先序遍历。建立一个栈,当指针到达根结点时,打印根结点,并进栈,判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点,然后弹栈判断前一元素是否有右结点一直到有右结点为止,有右结点后将其右结点作为根结点重复上述步骤直到栈为空并且左
2右指向子结点的指针都为空结束循环即完成了先序遍历
(5)中序遍历。建立一个栈,当指针到达根结点时,结点进栈,判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点,然后弹栈,每次弹栈都读取结点,然后判断前一元素是否有右结点一直到有右结点为止,有右结点后将其右结点作为根结点重复上述步骤直到栈为空并且左右指向子结点的指针都为空结束循环即完成了中序遍历
(6)后序遍历。建立一个栈,并建立一个数组,数组伴随进栈出栈更改对应的值,数组里的数值代
进栈次数,1代表进栈1次,2代表进栈两次。当指针到达根结点时,进栈,判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点,然后弹栈判断前一元素是否有右结点若没有或已经进栈两次则读取结点的值并继续弹栈,一直到有右结点且只进过一次栈为止,然后将其第二次进栈,并将其右结点作为根结点重复上述步骤直到栈为空并且左右指向子结点的指针都为空结束循环即完成了后序遍历。
3二算法
开始t传入根结点t==null。结点是否为空no结束yesvisit(t)打印根结点的值t->child访问左子结点t->child访问右子结点
表1递归先序流程图
4
开始t结束t==null。t->childvisit(t)
表2递归中序遍历流程图
t->child5
开始t结束t==null。t->childt->child
表3递归后序遍历流程图
visit(t)
6
开始t,st传入树根指针,和栈指针a=t;b=t;aa。=null有左子结点yesvisit(a);intostack(st,a);a=a->lchild;nooutstack(st,&b);yesb=b->rchild;yesst->top。=1栈不空nobvisit(b);intostack(st,b);a=b->lchild;b。=null有右子结点yesnost->top。=1&&b==null栈不空且没有右子结点yesoutstack(st,&b);b=b->rchild;st->top。=1&&(a。=null||b。=null)栈不空且有子节点no结束no
表4非递归先序遍历流程图
7开始t,sta=t;b=t;aa。=nullnooutstack(st,&b);visit(b);yesb=b->rchild;yesintostack(st,a);a=a->lchild;st->top。=1yesbb。=nullyesnointostack(st,b);a=b->lchild;nointostack(st,b);a=b->lchild;yesnob。=nullst->top。=1&&b==nullyesoutstack(st,&b);visit(b);b=b->rchild;no结束表5非递归后序遍历流程图
st->top。=1&&(a。=null||b。=null)no
8开始t,sta=t;b=t;inti[max];intj=0;aa。=nullnooutstack(st,&b);--j;a=b;b=b->rchild;yesintostack(st,a);i[j++]=1;a=a->lchild;yesst->top。=1yesbb。=nullnonoyesintostack(st,a);i[j++]=2;intostack(st,b);i[j++]=1;a=b->lchild;visit(a);intostack(st,a);i[j++]=2;intostack(st,b);i[j++]=1;a=b->lchild;yesvisit(a);a=null;b=null;noi[j]。=2&&b。=nullst->top。=1&&b==nullyesoutstack(st,&b);--j;a=b;b=b->rchild;no结束st->top。=1&&(a。=null||b。=null)no
表6非递归后序遍历流程图
9三源代码
#include#include#definesizesizeof(bitreea)#definemax500typedefstructbitreea{chardata;structbitreea*lchild,*rchild;}bitreea,*b;//树结点typedefstructstack{inttop;
bs[max];}stack;//创建栈
voidintostack(stack*st,bin){
if(st->top==max-1){printf(”wrong”);}
st->s[(st->top)++]=in;}//进栈函数
voidoutstack(stack*st,b*out){
if(st->top==0){printf(”wrong”);}
*out=st->s[--(st->top)];}//出栈函数voidvisit(bt){if(t->data。=‘#’){printf(”%c”,t->data);}}//访问结点的值
10intcreatbitree(b&t){chardata;scanf(”%c”,&data);if(data==‘#’){t=null;}else{
t=(bitreea*)malloc(sizeof(bitreea));
t->data=data;
creatbitree(t->lchild);creatbitree(t->rchild);}return(0);}//先序创建二叉树//递归遍历二叉树intpre(bt){if(t。=null){visit(t);pre(t->lchild);pre(t->rchild);}}//先序遍历intzhong(bt){if(t。=null){
zhong(t->lchild);visit(t);zhong(t->rchild);}}//中序遍历inthou(bt){if(t。=null){hou(t->lchild);
hou(t->rchild);
11}visit(t);}//后序遍历
//非递归遍历
intfpre(bt,stack*st){ba,b;a=t;b=t;
do{
if(a。=null){visit(a);intostack(st,a);a=a->lchild;}
else
{if(st->top。=1)
{outstack(st,&b);b=b->rchild;
if(b。=null)
{
visit(b);intostack(st,b);a=b->lchild;
}
else{while(st->top。=1&&b==null){outstack(st,&b);b=b->rchild;
if(b。=null){visit(b);intostack(st,b);a=b->lchild;
}
}
}
}
}
}while(st->top。=1&&(a。=null||b。=null));}//先序遍历intfzhong(bt,stack*st){ba,b;a=t;b=t;
do{
12
if(a。=null){intostack(st,a);a=a->lchild;}
else
{if(st->top。=1)
{
outstack(st,&b);visit(b);b=b->rchild;if(b。=null)
{
intostack(st,b);a=b->lchild;
}
else{while(st->top。=1&&b==null){outstack(st,&b);visit(b);b=b->rchild;
if(b。=null){intostack(st,b);a=b->lchild;
}
}
}
}
}
}while(st->top。=1&&(a。=null||b。=null));}//中序遍历intfhou(bt,stack*st){ba,b;a=t;b=t;inti[max];intj=0;
do{
if(a。=null){intostack(st,a);i[j++]=1;a=a->lchild;}
else
{if(st->top。=1)
{
outstack(st,&b);--j;a=b;b=b->rchild;if(b。=null){
13
intostack(st,a);i[j++]=2;intostack(st,b);i[j++]=1;a=b->lchild;
}
else{visit(a);while(st->top。=1&&b==null){outstack(st,&b);--j;a=b;b=b->rchild;
if(i[j]。=2&&b。=null){intostack(st,a);i[j++]=2;intostack(st,b);i[j++]=1;
a=b->lchild;
}else{
visit(a);a=null;b=null;
}
}
}
}
}
}while(st->top。=1&&(a。=null||b。=null));}//后序遍历intmain{
stackst;st.top=1;bss;creatbitree(ss);printf(”递归:\n\n”);printf(”
先序:”);pre(ss);printf(”\n\n”);printf(”
中序:”);zhong(ss);printf(”\n\n”);printf(”
后序:”);hou(ss);
14printf(”\n\n”);printf(”非递归:\n\n”);printf(”
先序:”);fpre(ss,&st);printf(”\n\n”);printf(”
中序:”);fzhong(ss,&st);printf(”\n\n”);printf(”
后序:”);fhou(ss,&st);printf(”\n\n”);system(”pause”);}//主函数
15四运行结果
表7运行结果
五遇到的问题及解决
1遇到的问题:
(1)在非递归遍历中遇到结点值两次进栈的问题,在弹栈过程中虽然弹出同一值但根据进栈的次数不同处理方式不同必须有一标示指出结点是否已进过两次栈。
(2)树结点的返回查找问题,由于二叉树总是由根节点指向子节点的所以查到左子节点就不能查找右节点了。
2解决方法:
(1)创建了一个数组数组里的每一项存的值会根据结点的进栈出栈做出相应的改变在进行处理是添加对数组值得判断以保证结点不会第三次进栈。
(2)创建一个栈来保存根节点,当需要查询右节点是弹栈返回查找右节点。
16六心得体会
课程设计期间,遇见一些问题,一个就是怎样后序非递归遍历二叉树,经过分析和斟酌,终于得到比较满意的程序,使得这个程序变得有一点意义。这一次的课程设计给我们提供了一个既能动手又动脑,独立实践的机会,应该紧紧抓住这个机会把所学的专业课程进一步的巩固和加深,进一步培养我们的综合能力。灵活运用各种数据类型组成一个具有系统性的程序。在这之中,虽然每个人的思路不一样,但是拿一颗真诚热心去探讨问题就能更好的解决问题。我们应该更能了解我们自己,自己还是太嫩,需要我们学习的还有很多很多,成功是百分之九十九的汗