二叉树的遍历学习心得.docx

二叉树的遍历学习心得
二叉树的非递归遍历学习心得
对于学习数据结构的新手来说，二叉树应该是遇到的一个比较大的难题。对于二叉树的遍历，如果使用递归的方法，代码非常简单，但是有些程序语言不支持递归，而且递归的执行效率偏低，使许多程序设计人员望而却步下面我将与大家分享我在学习二叉树的非递归遍历的过程中遇到的困惑与解答，以供学习和交流。
鉴于有些数据结构资料中没有介绍树的结点的栈的结点的构造，首先向大家介绍结点的构造。
typedefstructbitnode{chardata;
\树的结点的数据域（以字符型数据为
\树的结点的结构
例）
structbitnode*lchild，*rchild;
\树的子树指针
}bitnode，*bittree;
typedefstructnode{bitnodestack;
\栈的数据域类型为树的结点
\栈的结点结构
structnode*next;}linkstack;遍历的前提当然是二叉树存在，下面为大家介绍树的建立。bittreecreat_bittree{
bittreebt;
\树的根结点charx;scanf（"%c"，x）;
\树的建立的子函数类型为树的指针类型
}if（x=='X'）bt=null;else{
}returnbt;
\如果输入为’X’，则返回空结点
bt=（bittree）malloc（sizeof（bitnode））;\若输入有效，则申请结点空间bt->data=x;
\装填结点\插入左子树\插入右子树bt->lchild=creat_bittree;bt->rchild=creat_bittree;
建立二叉树的过程使用了递归，如果理解不了，可以自己画图助于理解，建立决定了二叉树的形状，一定要弄清楚。如所要建立的二叉树的形状为
那么输入应该为abdXXeg
。
接下来是栈的一些操作，因为任何一本数据结构的资料都会在栈和队列的章节说得很清楚，下面只是做了一些比较小的改动，请读者自行体会。intinit_stack（linkstack**s）{
}
intpush_stack（linkstack*s，bitnode*x）
*s=（linkstack*）malloc（sizeof（linkstack））;（*s）->next=null;return1;{
}
intpop_stack（linkstack*s，bitnode*e）{
return0;}
}
intempty_stack（linkstack*s）{
}
if（s->next==null）return1;return0;linkstack*p;
if（empty_stack（s））{printf（"stackisnull\n"）;p=s->next;s->next=p->next;*e=p->stack;free（p）;return1;linkstack*p;
p=（linkstack*）malloc（sizeof（linkstack））;p->stack=*x;p->next=s->next;s->next=p;return1;先介绍先序遍历的算法，先建立根结点，再建立左子树再到右子树，遍历是相对于每一棵子树来说的，这一点要格外注意。最重要的是要在脑海里建立模型，在后面的后序遍历中尤显模型的重要性。voidpre_order（bittreet）{
}以下是主函数。intmain{
bittreet;
printf（"\n\t********************欢迎来到二叉linkstack*s;bittreep;p=t;
init_stack（s）;push_stack（s，p）;while（。empty_stack（s））{
pop_stack（s，p）;
printf（"\t[%c]"，p->data）;
if（p->rchild）push_stack（s，p->rchild）;if（p->lchild）push_stack（s，p->lchild）;}树世界********************\n"）;
printf（"\n\t请输入二叉树结点，"X"为空树\n\t"）;t=creat_bittree;printf（"\n"）;
printf（"\t先序遍历二叉树如下："）;printf（"\n"）;
}
pre_order（t）;printf（"\n\t"）;getch;以下是二叉树的中序遍历的算法，先从左子树入栈到底，然后访问栈顶元素，同时栈顶出栈，再检测是否存在右子树，如果存在，从它的右子树的左子树入栈到底，如果不存在，访问栈顶元素，同时栈顶出栈，如此循环，直到栈空。voidin_order（bittreet）{
}
linkstack*s;bittreep，q;
q=（bittree）malloc（sizeof（bitnode））;p=t;
init_stack（s）;
while（p||。empty_stack（s））{if（p）{
}else{
}}
pop_stack（s，q）;
printf（"\t[%c]"，q->data）;p=q->rchild;push_stack（s，p）;p=p->lchild;二叉树的遍历中要数后序遍历最为复杂，它的栈的构造与前面两种遍历方法有所不同，在栈里加了一个标记元素rvisited用来标记其结点的右子树是否被访问过，由此来达到最后才访问根结点的效果。由于程序比较复杂，下面为大家一步步分析。
typedefstructnode{
}linkstack;intpush_stack（linkstack*s，bitnode*x）{
}voidpost_order（bittreet）{
bittreep，q;linkstack*s，*top;init_stack（s）;p=t;
q=（bittree）malloc（sizeof（bitnode））;while（p）
\从左子树插入到底{
linkstack*p;
p=（linkstack*）malloc（sizeof（linkstack））;p->stack=*x;p->rvisited=0;p->next=s->next;s->next=p;return1;
\插入栈的时候先设为右子树未被访问
intrvisited;bitnodestack;structnode*next;
\标记元素，记录右子树是否已被访问
}
push_stack（s，p）;p=p->lchild;
while（。empty_stack（s））{
top=s->next;
\取栈顶元素
if（。top->stack.rchild||top->rvisited）\若栈顶元素的右子树不存在或者被访问过，访问栈顶元素同时出栈
}else
\若栈顶元素的右子树存
{
pop_stack（s，q）;
printf（"\t[%c]"，q->data）;在而且未被访问过，先将其rvisited值设为1再向右检测右子树
}二叉树的几种遍历方法就介绍到这里，以上程序均在ＶＣ++6.0编译环境下运行通过，值得注意的是，三种遍历方法不能放在同一个程序中使用，因为树的遍历过程伴随着销毁，遍历一次以后下一次的遍历就变得毫无意义。由于本人水平有限，难免有纰漏差错之处，请谅解.
}}}{
top->rvisited=1;p=top->stack.rchild;while（p）{
push_stack（s，p）;p=p->lchild;
\从根结点的左子树插入栈到底参考文献
（稻草人）[1]徐孝凯.数据结构简明教程[m].北京：清华大学出版社，1995：71291.[2]严蔚敏，吴伟民.数据结构[m].北京：清华大学出版社，2000：962106.[3]耿国华.数据结构—c语言描述[m].西安：西安电子科技大学出版社，2006：1012104.[４]崔进平，郭小春，王霞.数据结构（Ｃ语言版）[m].北京：清华大学出版社，2011：245868.
（稻草人）
第7页 共7页