第四章：树与二叉树（二叉树的遍历和线索二叉树）

上一篇文章讲了第四章的数据结构：树和二叉树(二叉树的顺序存储和链式存储)。下面学习二叉树和线索二叉树的遍历(数据结构相关文章在理木客,微信官方账号同步更新，同名，欢迎关注)。

1.二叉树的遍历

二叉树的遍历:按照一定的搜索路径访问树中的每个节点。树中的每个节点只被访问一次。

根据访问根节点的顺序，我们将其分为

优先遍历：先行根-左子树-右子树

中间顺序遍历：第一个左子树-根-右子树

后序遍历：先左子树-右子树-根

注意，每当根访问时，它总是首先访问左子树，然后访问右子树。

1.1先序遍历

前序遍历：

访问根节点；

递归遍历左侧子树；

递归遍历右边的子树；

注意：每个节点的分支遵循上述访问顺序，反映了“递归调用”

时间复杂度:不适用

上图先序遍历结果:阿卜德费奇

思维过程：

(1)首先访问根节点a，

(2)将A分为左子树和右子树。因为是递归调用，所以左子树也遵循‘先根节点-后左-后右’的顺序，所以访问的是节点B。

(3)然后访问节点d，

(4)访问节点F时，有分支，也遵循‘先根节点-再左-再右’的顺序。

(5)访问节点E，当左边的大的子树已经被访问。

(6)然后按照最后一次访问右边子树的顺序，访问右边的大子树，右边的大子树也会先访问根节点c。

(7)访问左子树g，

(8)因为没有G的左子树，接下来访问G的右子树H，

(9)最后访问C的右边子树I。

优先遍历的递归算法；

voidPreOrder(BiTreeT){if(T！=null){ visit(T)；前序(T-l child)；前序(T-rchild)；}}

1.2中序遍历

按照左子树-根节点-右子树的顺序访问。

中间顺序遍历：

用中间顺序遍历左子树；

访问根节点；

用中间顺序遍历右边的子树。

时间复杂度:不适用

上图中序遍历结果:DBEFAGHCI

中序遍历的递归算法：

voidPreOrder(BiTreeT){if(T！=null){ PreOrder(T-l child)；访问(T)；前序(T-rchild)；}}

1.3后序遍历

按照左子树-右子树-根节点的顺序访问。

后序列遍历：

用postorder递归遍历左子树；

使用后序递归遍历右边的子树；

访问根节点；

时间复杂度:不适用

上图后序遍历的结果:DEFBHGICA

后序遍历的递归算法：

voidPreOrder(BiTreeT){if(T！=null){ PreOrder(T-l child)；前序(T-rchild)；访问(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：右孩子结点进栈后，依次将该节点的左侧结点依次进栈，然后继续循环步骤二，知道栈为空

代码实现：

voidInOrder2(BiTreeT){InitStack(S);BiTreep=T;//循环判断while(p||!IsEmpty(S)){//栈非空if(p){Push(S,p);p-p->lchild;//将p指向左孩子}else{Pop(S,p);//左孩子为空，出栈一个结点visit(p);//并访问它p=p->rchild;//指向右孩子}}}

3.层次遍历

层次遍历：顾名思义，从上到下从左到右依次遍历，遍历顺序及时标号顺序。

层次遍历需要借助队列，算法思想：

·初始将根入队并访问根结点

·若有左子树，则将左子树的根入队

·若有右子树，则将右子树的根入队

·然后出队节点并访问

·反复该过程直到队列为空

代码实现：

voidleveOrder(BiTreeT){InitQueue(Q);BiTreep;//辅助变量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。

5.2中序线索化

5.3后序线索化

最常用的还是中序线索二叉树

显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag

线索二叉树的结点结构

typedefstructThreadNode{ElemTypedata;structThreadNode*lchild,*rchild;intltag,rtag;}ThreadNode,*ThreadTree;

这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表。对于指向前驱和后继的指针称为线索，线索化的二叉树就称为：线索二叉树

5.4中序线索二叉树

中序线索二叉树线索化代码

//传入一个根节点和前驱结点voidInThread(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);//递归右子树线索化}}

初始化和收尾

//传入线索二叉树的根节点voidCreateInThread(ThreadTreeT){ThreadTreepre=NULL;if(T!=NULL){InThread(T,pre);//实现线索化pre->rchild=NULL;//收尾最后遍历的结点的右孩子至为空pre->rtag=1;}}

引入头节点的线索二叉树

中序线索二叉树的遍历

//找最左侧的孩子结点ThreadNode*Firstnode(ThreadNode*p){while(p->ltag==0){p=p->lchild;}returnp;}//找后继结点ThreadNode*Nextnode(ThreadNode*p){if(p->rtag==0){returnFirstnode(p->rchild);}returnp->rchild;}voidInOrder(ThreadNode*T){for(ThreadNode*p=Firstnode(T);p!=NULL;p=Nextnode(p)){visit(p);}}

持续更新中~

往期文章：

学习数据结构--第一章：绪论

学习数据结构--第二章：线性表(顺序存储、插入、删除)

数据结构第二章：线性表(链式存储、单链表、双链表、循环链表)

学习数据结构--第二章：线性表(顺序表VS链表)

学习数据结构--第三章：栈和队列（栈的基本操作）

数据结构-第三章：栈和队列（队列的基本操作、循环、双端队列）

数据结构-第三章：栈和队列（栈的应用、括号匹配、表达式转换）

学习数据结构--第三章：栈和队列（特殊矩阵的压缩存储）

数据结构第四章：树与二叉树（树的基本概念、基本术语、性质）

数据结构第四章：树与二叉树（二叉树的概念、性质、特殊二叉树）

数据结构第四章：树与二叉树（二叉树的顺序存储和链式存储）