数据结构 之 线索二叉树（七）

提示：本篇主要讲解线索二叉树的基本概念和二叉树、树，森林之间的转换

线索二叉树基本概念

`提示：【问题】有n个结点的二叉链表中，有（ ）个指针域被闲置。

所以可以利用这些空闲的指针域：
当某结点无左孩子时，令其左指针指向它的前趋结点；
当该结点无右孩子时，令其右指针指向它的后继结点。

线索：指向前驱或后继结点的指针称为线索。

为了严格区分结点的孩子指针域究竟指向孩子结点还是指向前趋或后继结点， 需在原结点结构中增加两个标志域。 因此二叉链表的结点结构可重新定义为：

线索二叉树类型定义

struct thrnode {　　
		int  data;
　　		struct  thrnode  *lchild , *rchild;
　　 　　int Ltag，Rtag; /* 左、右标志域 */
　　 　　};

对二叉树以某种次序进行遍历并且加上线索的过程称为线索化。经过线索化后生成的二叉链表称为线索二叉树。

根据遍历的顺序，线索二叉树可以分为

1. 前序线索二叉树
2. 中序线索二叉树
3. 后序线索二叉树

线索二叉树的基本概念

中根线索二叉树

中根遍历序列：DBGEACF

树向二叉树的转换

方法：树中结点的孩子放在二叉树的左子树中，树中结点的兄弟放在二叉树的右子树中，简而言之就是，左孩子右兄弟。

转换步骤：
（1）在兄弟节点之间连一条线；
（2）每个结点仅保留其与最左孩子之间的连线，其余连线删除；
（3）以根为轴心将整棵树顺时针旋转45度。

树向二叉树的转换如图所示：

那么问题来了，思考：如何将一棵二叉树还原成树？

还原步骤如下：
（1）将二叉树中的根结点与其右孩子间的连线，及沿右分支搜索到的所有右孩子间的连线全部抹掉，使之变成孤立的二叉树；
（2）根据左孩子右兄弟法则，进行连接，结果下图所示。
（3） 逆时针旋转45°。

森林转换二叉树

可以看出这和树向二叉树的转换相同，只不过最后把多个二叉树合并成了一个而已，遵循的规则还是左孩子右兄弟原则.

树和森林的遍历(知道即可）

结论：
树的先根遍历序列与其转换后对应的二叉树的先根遍历序列序列相同。
树的后根遍历序列与其转换后对应的二叉树的中根遍历序列相同。