二叉树的遍历学习心得由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“看懂二叉树的三种遍历”。
二叉树的非递归遍历学习心得
对于学习数据结构的新手来说，二叉树应该是遇到的一个比较大的难题。对于二叉树的遍历，如果使用递归的方法，代码非常简单，但是有些程序语言不支持递归，而且递归的执行效率偏低，使许多程序设计人员望而却步下面我将与大家分享我在学习二叉树的非递归遍历的过程中遇到的困惑与解答，以供学习和交流。
鉴于有些数据结构资料中没有介绍树的结点的栈的结点的构造，首先向大家介绍结点的构造。
typedef struct BitNode { char data;
树的结点的数据域（以字符型数据为
树的结点的结构
例）
struct BitNode *lchild,*rchild;
树的子树指针
}BitNode,*BitTree;
typedef struct node { BitNode stack;
栈的数据域类型为树的 结点
栈的结点结构
struct node *next;}LinkStack;遍历的前提当然是二叉树存在，下面为大家介绍树的建立。BitTree Creat_BitTree(){
BitTree bt;
树的根结点 char x;scanf(“%c”,&x);
树的建立的子函数类型为树的指针类型
} if(x=='#')bt=NULL;else {
} return bt;
如果输入为’#’，则返回空结点
bt=(BitTree)malloc(sizeof(BitNode));若输入有效，则申请结点空间 bt->data=x;
装填结点 插入左子树 插入右子树 bt->lchild=Creat_BitTree();bt->rchild=Creat_BitTree();
建立二叉树的过程使用了递归，如果理解不了，可以自己画图助于理解，建立决定了二叉树的形状，一定要弄清楚。如所要建立的二叉树的形状为
那么输入应该为ABD##EG###。
接下来是栈的一些操作，因为任何一本数据结构的资料都会在栈和队列的章节说得很清楚，下面只是做了一些比较小的改动，请读者自行体会。int Init_Stack(LinkStack **s){
}
int Push_Stack(LinkStack *s,BitNode *x)
*s=(LinkStack*)malloc(sizeof(LinkStack));(*s)->next=NULL;return 1;{
}
int Pop_Stack(LinkStack *s,BitNode *e){
return 0;}
}
int Empty_Stack(LinkStack *s){
}
if(s->next==NULL)return 1;return 0;LinkStack *p;
if(Empty_Stack(s)){ printf(“Stack is NULLn”);p=s->next;s->next=p->next;*e=p->stack;free(p);return 1;LinkStack *p;
p=(LinkStack*)malloc(sizeof(LinkStack));p->stack=*x;p->next=s->next;s->next=p;return 1;先介绍先序遍历的算法，先建立根结点，再建立左子树再到右子树，遍历是相对于每一棵子树来说的，这一点要格外注意。最重要的是要在脑海里建立模型，在后面的后序遍历中尤显模型的重要性。void Pre_Order(BitTree T){
} 以下是主函数。int main(){
BitTree T;
printf(“nt********************欢迎来到二叉LinkStack *s;BitTree p;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(“nt请输入二叉树结点，”#“为空树nt”);T=Creat_BitTree();printf(“n”);
printf(“t先序遍历二叉树如下：”);printf(“n”);
}
Pre_Order(T);printf(“nt”);getch();以下是二叉树的中序遍历的算法，先从左子树入栈到底，然后访问栈顶元素，同时栈顶出栈，再检测是否存在右子树，如果存在，从它的右子树的左子树入栈到底，如果不存在，访问栈顶元素，同时栈顶出栈，如此循环，直到栈空。void In_Order(BitTree T){
}
LinkStack *s;BitTree p,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用来标记其结点的右子树是否被访问过，由此来达到最后才访问根结点的效果。由于程序比较复杂，下面为大家一步步分析。
typedef struct node {
}LinkStack;int Push_Stack(LinkStack *s,BitNode *x){
} void Post_Order(BitTree T){
BitTree p,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;return 1;
插入栈的时候先设为右子树未被访问
int rvisited;BitNode stack;struct node *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.(稻草人)
目录一 设计思想 ..........................................2 1递归遍历二叉树算法思想：.......................................2 2非递归遍历二叉树算法思想：.................
数据结构程序设计报告学院： 班级： 学号：姓名：实验名称：二叉树的建立与遍历一、实验目的：1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法；3.掌握二叉树的先序、中序、后序的......
# include # include typedef int Etype; typedef struct BiTNode /* 树结点结构 */{ Etype data;struct BiTNode *lch,*rch;}BiTNode; /* 函数原形声明 */ BiTNode *cr......
实验三 二叉树遍历算法一、实验目的1． 进一步理解掌握二叉树二叉链表存储结构。 2． 掌握二叉树遍历的递归与非递归算法。二、实验要求1． 认真阅读和掌握（先序、中序、后序和层次......
一、二叉链表的声明 .BinaryNode public cla BinaryNode //二叉树的二叉链表结点类，泛型T指//定结点的元素类型 {public T data;//数据域，存储数据元素public BinaryNode left......
