笔趣阁

第327章 半（第1页）

设一棵二叉树有n个结点，则有n-条边指针连线，而n个结点共有n个指针域

l+个空闲指针域未用。则可以利用这些空闲的指针域来存放结

点的直接前驱和直接后继信息。

为避免混淆，对结点结构加以改进，增加两个标志域，如图所示。用这种结点结构构成

的二叉树的存储结构；叫做线索链表；指向结点前驱和后继的指针叫做线索；

、线索二叉树的构建

按照某种次序遍历，加上线索的二叉树称之为线索二叉树。线索化二叉树:二叉树的线

索化指的是依照某种遍历次序使二叉树成为线索二叉树的过程。

线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继的过程。

【o年】若x是后序线索二叉树中的叶结点，且x存在左兄弟结点y，则x的右

线索指向的是______。

ax的父结点b以y为根的子树的最左下结点

cx的左兄弟结点yd以y为根的子树的最右下结点

【o年】若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分

别是______。

a．e、cb．e、ac．d、cd．b、a考点：树和二叉树（★★★）

、树转化为二叉树

对于一般的树，可以方便地转换成一棵唯一的二叉树与之对应。将树转换成二叉树在“孩

子兄弟表示法”中已给出，其详细步骤是：

加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。

去连线。除最左的第一个子结点外，父结点与所有其它子结点的连线都去掉。

旋转。将树顺时针旋转o，原有的实线左斜。

整型。将旋转后树中的所有虚线改为实线，并向右斜。

这样转换后的二叉树的特点是：

◆二叉树的根结点没有右子树，只有左子树；

◆左子结点仍然是原来树中相应结点的左子结点，而所有沿右链往下的右子结点均是原来

树中该结点的兄弟结点。

由于二叉树和树都可用二叉链表作为存储结构，对比各自的结点结构可以看出，以二叉

链表作为媒介可以导出树和二叉树之间的一个对应关系。

◆从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。

◆从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。

、二叉树转换成树

对于一棵转换后的二叉树，如何还原成原来的树?其步骤是：

（）加虚线。若某结点i是其父结点的左子树的根结点，则将该结点i的右子结点以及沿右

子链不断地搜索所有的右子结点，将所有这些右子结点与i结点的父结点之间加虚线相连，

如图a所示。

（）去连线。去掉二叉树中所有父结点与其右子结点之间的连线，如图b所示。

（）规整化。将图中各结点按层次排列且将所有的虚线变成实线，如图c所示。

、森林转换成二叉树

转换步骤：

将f={t，t，?，tn}中的每棵树转换成二叉树。

按给出的森林中树的次序，从最后一棵二叉树开始，每棵二叉树作为前一棵二叉树的

根结点的右子树，依次类推，则第一棵树的根结点就是转换后生成的二叉树的根结点，如图

所示。

、二叉树转换成森林

上述转换规则是递归的，可以写出其递归算法。以下给出具体的还原步骤。