大话数据结构-6.10 线索二叉树 188- 高飞网

6.10 线索二叉树 188

2016-12-26 23:31:49.0

6.10 线索二叉树

6.10.1 线索二叉树原理

    一个二叉树,有n个结点,每个结点有2个指针域,因此共有2n个指针域;而n个结点的二叉树,一共有n-1条分支线数,因此,存在着2n-(n-1)=n+1个空指针域,非常浪费。


    另外,遍历上面的二叉树时,得到HDIBJEAFCG这样的字符串序列,我们知道I的前驱是D,后继为B等等,但如果没有遍历,则只会知道每个结点的后继,不知道其前驱,要想知道必须遍历一遍。

    综合以上两个角度,可以考虑复用那些空地址,存放指向结点在某种遍历次序下的前驱和后继点的地址。把这种指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索链表,相应的二叉树就称为线索二叉树(Threaded Binary Tree)

    将这棵二叉树进行中序遍历后,将所有空指针域中的rchild,改为指向它的后继结点,于是有:

    同样,将这棵二叉树的所有空指针域中的lchild,改为指向当前结点的前驱,于是有:

    通过下图,更容易看出,其实线索二叉树,等于把一棵二叉树转变成了一个双向链表,这样对我们的插入删除结点都带来了方便。把对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

6.11 树、森林与二叉树的转换

    前面已经讲过了树的定义和存储结构,对于树来说,在满足树的条件下可以是任意形状,一个结点可以有任意多个孩子,显然对树的处理要复杂得多,去研究关于树的性质和算法,真的不容易,有没有简单的办法解决树处理的难题呢?

    对于二叉树,尽管它也是树,但由于每个结点最多只能有左孩子和右孩子,面对的变化就少了很多。因此许多性质和算法都被研究了出来。如果所有的树都像二叉树一样方便就好了,因此要想办法将其他的树转为二叉树。

    在讲树的存储结构时,提到了树的孩子兄弟法可以将一棵树用二叉链表进行存储,所以借助二叉链表,树和二叉树可以相互进行转换。

6.11.1 树转换为二叉树

  1. 加线。在所有兄弟结点之间加一条连线
  2. 去线。对树中每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线。
  3. 层次调整。以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明。注意第一个孩子是二叉树的左孩子,兄弟转换过来的孩子也是结点的右孩子。

6.11.2 森林转换为二叉树

    森林是由若干棵树组成的,所以完全可以理解为,森林中的每一棵树都是兄弟,可以依照兄弟的处理办法来操作。

  1. 把每棵树转换为二叉树
  2. 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

6.11.3 二叉树转为树

    二叉树转换树是树转换二叉树的逆过程。

  1. 加线。若某个结点的左孩子存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点...反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子用线连接起来。
  2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。
  3. 层次调整。

6.11.4 二叉树转为森林

    判断一棵二叉树能够转换成一棵树还是森林,标准很简单,那就是只要看这棵二叉树的根结点有没有右孩子,有就是森林,没有就是一棵树。那么如果是转换成森林,如下:

  1. 从根结点开始,若右孩子存在,则把与右孩结点的连线删除,再查看分离后的二叉树,若右孩子存在,则连接删除……,直到所有右孩子连线都删除为止,得到分离的二叉树。
  2. 再将每棵分离后的二叉树转换为树即可。


6.11.5 树与森林的遍历

    树的遍历分为两种:

  1. 一种是先根遍历树,即先访问树的根结点,然后依次先根遍历根的每棵子树。
  2. 另一种是后根遍历,即先依次后根遍历每棵子树,然后再访问根结点。如图6-11-4中最右侧的树,它的先根遍历序列为ABEFCDG,后根遍历序列为EFBCGDA

    森林的遍历也分为两种:

  1. 前序遍历:先访问森林中第一棵树的根结点,然后再依次遍历根的每棵子树,再依次同样方式遍历除去第一棵树的剩余树构成的森林。
  2. 后序遍历:是先访问森林中的第一棵树,后根遍历的方式遍历每棵子树,然后再访问根结点,再依次同样方式遍历除去第一棵树的剩余构成的森林。