数据结构二叉树建立与遍历代码（学习数据结构第四章）
数据结构二叉树建立与遍历代码（学习数据结构第四章）· 访问根节点；先序遍历：· 中序遍历：先左子树->根->右子树· 后序遍历：先左子树->右子树->根注意无论根什么时候访问，都是先访问左子树后访问右子树。
第四章：树与二叉树（二叉树的遍历和线索二叉树）上篇文章中讲了数据结构第四章：树与二叉树（二叉树的顺序存储和链式存储） 下面学习二叉树的遍历和线索二叉树 （数据结构相关文章在同名公众号 理木客 同步更新，欢迎关注）
1.二叉树的遍历二叉树的遍历：按某条搜索路径访问树中的每个结点 树的每个结点均被访问一次 而且只访问一次。
我们按照访问根结点的顺序分为
· 先序遍历：先根->左子树->右子树
· 中序遍历：先左子树->根->右子树
· 后序遍历：先左子树->右子树->根
注意无论根什么时候访问，都是先访问左子树后访问右子树。
1.1先序遍历先序遍历：
· 访问根节点；
· 采用先序递归遍历左子树；
· 采用先序递归遍历右子树；
注：每个节点的分支都遵循上述的访问顺序，体现"递归调用"
时间复杂度：O(n)
上图先序遍历结果：A BDFE CGHI
思维过程：
· (1) 先访问根节点A，
· (2)A分为左右两个子树，因为是递归调用，所以左子树也遵循"先根节点-再左-再右"的顺序，所以访问B节点，
· (3) 然后访问D节点，
· (4) 访问F节点的时候有分支，同样遵循"先根节点-再左--再右"的顺序
· (5) 访问E节点，此时左边的大的子树已经访问完毕，
· (6) 然后遵循最后访问右子树的顺序，访问右边大的子树，右边大子树同样先访问根节点C
· (7) 访问左子树G
· (8) 因为G的左子树没有，所以接下来访问G的右子树H
· (9) 最后访问C的右子树I
先序遍历的递归算法：
void preOrder(BiTree T){ if(T!=null){ visit(T); PreOrder(T->lchild); PreOrder(T->rchild); }}
1.2中序遍历按照左子树->根节点->右子树的顺序访问
中序遍历：
· 采用中序遍历左子树；
· 访问根节点；
· 采用中序遍历右子树
时间复杂度：O(n)
上图中序遍历结果：DBEFAGHCI
中序遍历的递归算法：
void PreOrder(BiTree T){ if(T!=null){ PreOrder(T->lchild); visit(T); PreOrder(T->rchild); }}
1.3后序遍历按照左子树->右子树-->根节点的顺序访问
后序遍历：
· 采用后序递归遍历左子树；
· 采用后序递归遍历右子树；
· 访问根节点；
时间复杂度：O(n)
上图后序遍历的结果：DEFB HGIC A
后序遍历的递归算法：
void PreOrder(BiTree T){ if(T!=null){ PreOrder(T->lchild); PreOrder(T->rchild); visit(T); }}
2.二叉树的非递归遍历上述讲的三种遍历方法都是使用递归进行遍历，下面讲如何使用非递归算法遍历，我们需要借助 栈，以中序遍历为例：
算法思想
· 初始时依次扫描根结点和根节点的所有左侧结点并将它们依次进栈
· 出栈一个结点，访问它
· 扫描该结点的右孩子结点并将其进栈
· 依次扫描右孩子结点的所有左侧结点并—进栈
· 反复该过程直到栈空为止
注意区分扫描和访问
按照上面的算法思想讲解如上图二叉树，我们使用非递归算法遍历：
1：依次扫描根结点和根节点的所有左侧结点并将它们依次进栈
2：出栈一个结点并访问
3：接着扫描7号结点的右孩子结点并进栈，它的右孩子结点为空，故无任何结点压入栈中。
4：然后继续出栈4号结点并访问它
5：接着扫描4号结点的右孩子结点并进栈，它的右孩子结点为空，故无任何结点压入栈中。
6：然后继续出栈2号结点并访问它
7：接着扫描2号结点的右孩子结点并进栈，它的右孩子结点为5，故将5号结点压入栈中。
8：接着扫描5号结点的所有左侧结点并依次进栈，它的左侧结点为空，故无任何结点压入栈中。
9：然后继续出栈5号结点并访问它，同样他右孩子结点为空，无任何结点进栈。
10：接着出栈1结点并访问它。
11：同样扫描1结点的右孩子结点，依次进栈
12：右孩子结点进栈后，依次将该节点的左侧结点依次进栈，然后继续循环步骤二，知道栈为空
代码实现：
void InOrder2(BiTree T){ InitStack(S); BiTree p=T; //循环判断 while(p||!IsEmpty(S)){ //栈非空 if(p){ Push(S p); p-p->lchild; //将p指向左孩子 }else{ Pop(S p); //左孩子为空，出栈一个结点 visit(p); //并访问它 p=p->rchild; //指向右孩子 } }}
3.层次遍历层次遍历：顾名思义，从上到下从左到右依次遍历，遍历顺序及时标号顺序。
层次遍历需要借助队列，算法思想：
· 初始将根入队并访问根结点
· 若有左子树，则将左子树的根入队
· 若有右子树，则将右子树的根入队
· 然后出队节点并访问
· 反复该过程直到队列为空
代码实现：
void leveOrder(BiTree T){ InitQueue(Q); BiTree p; //辅助变量 EnQueue(Q T); //根节点入队 while(!isEmpty(Q)){ DeQueue(Q P); //出队队首元素 visit(p); //并访问 if(p->lchild!=NULL){ //左孩子节点不为空，入队 EnQueue(Q p->lchild); } if(p->rchild!=NULL){//右孩子节点不为空，入队 EnQueue(Q p->rchild); } }}
4.遍历结果逆置我们由一个二叉树可以得到遍历序列，那么我们是否可以通过遍历序列得到一个二叉树吗？
首先我们只通过一个遍历序列可以得到二叉树吗？例如先序遍历序列：124536，我们直到先遍历的肯定是根节点，但是2是左节点还是右节点缺无法确定，所以根据一个遍历序列无法全程逆置。
其实，(后)先序遍历序列和中序遍历序列可以确定一颗二叉树，而后续遍历序列和先序遍历序列不可以确定一颗二叉树。
在学习遍历结果逆置的时候请务必清楚三种遍历方式.
先序遍历序列和中序遍历序列逆置思想：
· 在先序序列中 第一个节点是根结点;
· 根结点将中序遍历序列划分为两部分;
· 然后在先序序列中确定两部分的结点 并且两部分的第一个结点分别为左子树的根和右子树的根;
· 在子树中递归重复该过程 便能唯一确定一棵二叉树。
例如：先序序列：124536 中序序列为：425163，请画出该二叉树。
先序遍历我们直到第一个结点时根节点，后序遍历序列我们知道最后一个结点为根结点，所以后序遍历序列加中序遍历序列的操作大同小异。
另外根据层次遍历序列和中序遍历序列也可以确定一个唯一二叉树。
5.线索二叉树上面讲到二叉链表，我们知道不管二叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n 1个。
因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点，这种指针称为线索。同时提升了查找速度。
我们称这个线索二叉树的建立过程为：线索化
若无左子树，则将左指针指向其前驱结点。若无右子树，则将右指针指向其后继结点。
5.1先序线索化结点1有左孩子2->结点2有左孩子->结点4没有左孩子故左指针指向前驱结点2->结点4没有右孩子故右指针指向后继结点5->结点5没有左孩子故左指针指向前驱结点->结点5没有右孩子故右指针指向后继结点3->结点3有左孩子6->结点6没有左孩子故左指针指向前驱节点3->结点6没有右孩子且没有后继结点->接着看结点3，它没有右孩子则将右指针指向后继结点6。
最常用的还是中序线索二叉树
显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag
线索二叉树的结点结构
typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild *rchild; int ltag rtag;}ThreadNode *ThreadTree;
这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表。对于指向前驱和后继的指针称为 线索，线索化的二叉树就称为：线索二叉树
5.4中序线索二叉树
中序线索二叉树线索化代码
//传入一个根节点和前驱结点void InThread(ThreadTree &p ThreadTree &pre){ if(p!=NULL){ InThread(p->lchild pre); //递归左子树线索化 if(p->lchild==NULL){ //没有左孩子 p->lchild = pre; //左孩子指针指向前驱 p->ltag = 1; //前驱线索 } if(pre!=NULL && pre->rchild==NULL){ //没有右孩子 pre->rchild = p; //前驱右孩子指针指向后继(当前结点p) pre->rtag = 1; //后继线索 } pre = p; //修改前驱结点为当前结点 InThread(p->rchild pre); //递归右子树线索化 }}
初始化和收尾
//传入线索二叉树的根节点 void CreateInThread(ThreadTree T){ ThreadTree pre=NULL; if(T!=NULL){ InThread(T pre); //实现线索化 pre->rchild=NULL; //收尾 最后遍历的结点的右孩子至为空 pre->rtag=1; } }
引入头节点的线索二叉树
中序线索二叉树的遍历
//找最左侧的孩子结点
ThreadNode *Firstnode(ThreadNode *p){
while(p->ltag==0){
p=p->lchild;
}
return p;
}
//找后继结点
ThreadNode *Nextnode(ThreadNode *p){
if(p->rtag == 0){
return Firstnode(p->rchild);
}
return p->rchild;
}
void InOrder(ThreadNode *T){
for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)){
visit(p);
}
}
持续更新中~
往期文章：
学习数据结构--第一章：绪论
学习数据结构--第二章：线性表(顺序存储、插入、删除)
数据结构第二章：线性表(链式存储、单链表、双链表、循环链表)
学习数据结构--第二章：线性表(顺序表VS链表)
学习数据结构--第三章：栈和队列（栈的基本操作）
数据结构-第三章：栈和队列（队列的基本操作、循环、双端队列）
数据结构-第三章：栈和队列（栈的应用、括号匹配、表达式转换）
学习数据结构--第三章：栈和队列（特殊矩阵的压缩存储）
数据结构第四章：树与二叉树（树的基本概念、基本术语、性质）
数据结构第四章：树与二叉树（二叉树的概念、性质、特殊二叉树）
数据结构第四章：树与二叉树（二叉树的顺序存储和链式存储）
