二叉树遍历_二叉树及其遍历
二叉树遍历由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“二叉树及其遍历”。
目录
一 设计思想..........................................2 1递归遍历二叉树算法思想：.......................................2 2非递归遍历二叉树算法思想：.....................................2
二 算法流程图........................................4 三 源代码............................................4 四 运行结果.........................................16 五 遇到的问题及解决.................................16 1遇到的问题：..................................................16 2解决方法：....................................................16 六 心得体会.........................................17
一 设计思想
1递归遍历二叉树算法思想：
（1）先序遍历：首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。若二叉树非空，则依次进行如下操作：（1）访问跟结点；（2）前序遍历左子树；（3）前序遍历右子树。
（2）中序遍历：首先判断根结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。若二叉树非空，则依次进行如下操作：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
（3）后序遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。若二叉树非空，则依次进行如下操作：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
2非递归遍历二叉树算法思想：
（4）先序遍历：建立一个栈，当指针到达根结点时，打印根结点，并进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈判断前一元素是否有右结点一直到有右结点为止，有右结点后将其右结点作为根结点重复上述步骤直到栈为空并且左 右指向子结点的指针都为空结束循环即完成了先序遍历
（5）中序遍历：建立一个栈，当指针到达根结点时，结点进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈，每次弹栈都读取结点，然后判断前一元素是否有右结点一直到有右结点为止，有右结点后将其右结点作为根结点重复上述步骤直到栈为空并且左右指向子结点的指针都为空结束循环即完成了中序遍历
（6）后序遍历：建立一个栈，并建立一个数组，数组伴随进栈出栈更改对应的值，数组里的数值代表进栈次数，1代表进栈1次，2代表进栈两次。当指针到达根结点时，进栈，判断是否有左子结点若有将左子结点作为根结点继续循环上述步骤。直到没有左子结点，然后弹栈判断前一元素是否有右结点若没有或已经进栈两次则读取结点的值并继续弹栈，一直到有右结点且只进过一次栈为止，然后将其第二次进栈，并将其右结点作为根结点重复上述步骤直到栈为空并且左右指向子结点的指针都为空结束循环即完成了后序遍历。二 算法流程图
开始T传入根结点T==Null？结点是否为空 No结束YesVisit（T）打印根结点的值T->child访问左子结点T->child访问右子结点
表1 递归先序流程图
开始T结束T==Null？ T->childVisit（T）
表2 递归中序遍历流程图
T->child5
开始T结束T==Null？ T->childT->child
表3 递归后序遍历流程图
Visit（T）
开始T，st传入树根指针，和栈指针a=T;b=T;aa！=Null有左子结点Yesvisit(a);IntoStack(st,a);a=a->lchild;NoOutStack(st,&b);Yes b=b->rchild;Yes St->top!=1栈不空No bvisit(b);IntoStack(st,b);a=b->lchild;b!=NULL有右子结点Yes No st->top!=1&&b==NULL栈不空且没有右子结点Yes OutStack(st,&b);b=b->rchild;st->top!=1&&(a!=NULL||b!=NULL)栈不空且有子节点No 结束No
表4 非递归先序遍历流程图 开始T，sta=T;b=T;aa！=NullNoOutStack(st,&b);visit(b);Yes b=b->rchild;YesIntoStack(st,a);a=a->lchild;St->top!=1Yes bb!=NULLYes No IntoStack(st,b);a=b->lchild;NoIntoStack(st,b);a=b->lchild;YesNob!=NULLst->top!=1&&b==NULLYes OutStack(st,&b);visit(b);b=b->rchild;No 结束表5 非递归后序遍历流程图
st->top!=1&&(a!=NULL||b!=NULL)No 开始T，sta=T;b=T;int i[max];int j=0;aa！=NullNoOutStack(st,&b);--j;a=b;b=b->rchild;YesIntoStack(st,a);i[j++]=1;a=a->lchild;Yes St->top!=1Yes bb!=NULLNoNo Yes IntoStack(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==NULLYes OutStack(st,&b);--j;a=b;b=b->rchild;No 结束st->top!=1&&(a!=NULL||b!=NULL)No
表6 非递归后序遍历流程图 三 源代码
#include #include #define size sizeof(Bitreea)#define max 500 typedef struct Bitreea{ char data;struct Bitreea *lchild,*rchild;}Bitreea,*B;//树结点 typedef struct stack {int top;
B s[max];}stack;//创建栈
void IntoStack(stack *st,B in){
if(st->top==max-1){printf(“wrong”);}
st->s[(st->top)++]=in;}//进栈函数
void OutStack(stack *st,B *out){
if(st->top==0){printf(“wrong”);}
*out=st->s[--(st->top)];}//出栈函数 void visit(B T){ if(T->data!='#'){printf(“%c ”,T->data);} }//访问结点的值int creatBitree(B &T){ char data;scanf(“%c”,&data);if(data=='#'){T=NULL;} else{
T=(Bitreea*)malloc(sizeof(Bitreea));
T->data=data;
creatBitree(T->lchild);creatBitree(T->rchild);}return(0);}//先序创建二叉树 //递归遍历二叉树 int pre(B T){ if(T!=NULL){visit(T);pre(T->lchild);pre(T->rchild);} }//先序遍历 int zhong(B T){ if(T!=NULL){
zhong(T->lchild);visit(T);zhong(T->rchild);} }//中序遍历 int hou(B T){ if(T!=NULL){ hou(T->lchild);
hou(T->rchild);} visit(T);}//后序遍历
//非递归遍历
int fpre(B T, stack *st){B a,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));} //先序遍历 int fzhong(B T, stack *st){B a,b;a=T;b=T;
do{
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));} //中序遍历 int fhou(B T, stack *st){B a,b;a=T;b=T;int i[max];int j=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){
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));} //后序遍历 int main(){
stack st;st.top=1;B;creatBitree();printf(“递归:nn”);printf(“
先序：”);pre();printf(“nn”);printf(“
中序：”);zhong();printf(“nn”);printf(“
后序：”);hou();printf(“nn”);printf(“非递归:nn”);printf(“
先序：”);fpre(,&st);printf(“nn”);printf(“
中序：”);fzhong(,&st);printf(“nn”);printf(“
后序：”);fhou(,&st);printf(“nn”);system(“pause”);}//主函数四 运行结果
表7 运行结果
五 遇到的问题及解决
1遇到的问题：
(1)在非递归遍历中遇到结点值两次进栈的问题，在弹栈过程中虽然弹出同一值但根据进栈的次数不同处理方式不同必须有一标示指出结点是否已进过两次栈。
(2)树结点的返回查找问题，由于二叉树总是由根节点指向子节点的所以查到左子节点就不能查找右节点了。
2解决方法：
（1）创建了一个数组数组里的每一项存的值会根据结点的进栈出栈做出相应的改变在进行处理是添加对数组值得判断以保证结点不会第三次进栈。
（2）创建一个栈来保存根节点，当需要查询右节点是弹栈返回查找右节点。六 心得体会
课程设计期间，遇见一些问题，一个就是怎样后序非递归遍历二叉树，经过分析和斟酌，终于得到比较满意的程序，使得这个程序变得有一点意义。这一次的课程设计给我们提供了一个既能动手又动脑，独立实践的机会，应该紧紧抓住这个机会把所学的专业课程进一步的巩固和加深，进一步培养我们的综合能力。灵活运用各种数据类型组成一个具有系统性的程序。在这之中，虽然每个人的思路不一样，但是拿一颗真诚热心去探讨问题就能更好的解决问题。我们应该更能了解我们自己，自己还是太嫩，需要我们学习的还有很多很多，成功是百分之九十九的汗水加上百分之一的灵感，所以我们的路还很长很长，或许是万里长城，或许还要翻山越岭，但是我们都应该永不放弃，不断提高，更好地运用课堂学习的知识。通过这次作业我学到了很多东西，将以前学过的C语言知识与现在的课堂知识进行结合应用。重要的是使我知道了自学知识和合作的重要性，提高了自己动手能力和沟通能力，学到了许多解决实际问题的宝贵经验．同时也挖掘出了我们潜在的能力，使我们对编程更有兴趣。我相信，只要努力、勤奋、坚持不懈，就没有什么做不到的事，不能还没开始就退缩，要勇于拼搏，敢于创新。总之，在通过又一次的真正动手之后，我在C语言设计方面获益匪浅，我会更加努力的学习编程方面的更多知识，提高自己的能力。然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优的也要想办法自己解决，然后和好的方案进行比较。
注：源代码可以优化，从流程图可以看出，自己修改了
