二叉树2 | 一个算法汪的日常

这是《大话数据结构》第六章树的内容，这里总结线索二叉树，二叉树、树和森林的转换以及赫夫曼树的知识点，其中赫夫曼树的总结是在做牛客网上的数据结构选择题的时候，遇到有关这个知识点的时候总结的内容，主要是通过百度得到的，也有结合书本的内容。

线索二叉树

线索二叉树原理

首先如下图所示的二叉树，其中^符号表示空指针域，对于一个有n个结点的二叉链表，每个结点都有指向左右孩子的两个指针域，所以一共有2n个指针域。而n个结点的二叉树是有n-1条分支线数，也就是存在$2n-(n-1)=n+1$个空指针域，这些空间是不存储任何东西，也就是浪费内存的资源。

另一方面，在对上图的二叉树做中序遍历时，可以得到HDIBJEAFCG这样的字符序列，通过这样的遍历，可以知道，结点I的前驱是D，后继是B。即我们可以知道任意一个结点的前驱和后继分别是哪个，但这是在经过遍历之后的结果，即每次使用都需要先遍历一次，才可以知道任意结点的前驱和后继。

综合上述两种情况，为了更好利用内存资源，节省时间，就有了线索二叉树了，我们将指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就是线索二叉树了。

线索化是对二叉树以某种次序遍历使其变为线索二叉树的过程。

我们对上图的二叉树按照中序遍历的方式进行线索化，可以得到下图，其中虚线箭头是表示后继，实线箭头是前驱。这里设置二叉树的左指针是指向前驱，右指针指向后继。

但是增加了线索后，需要解决的问题就是如何判断当前结点的左指针是指向其左孩子，还是前驱呢。这里就需要在每个结点增加两个标志域ltag和rtag，用来表示左右指针指向的是左右孩子还是前驱或者后继。

线索二叉树结构实现

二叉树的线索存储结构定义如下：

 // Link == 0 表示指向左右孩子指针； Thread == 1 表示指向前驱或者后继的线索
typedef enum {Link, Thread} PointerTag;

// 二叉树线索存储结点结构
typedef struct BiThrNode
{
	// 结点数据  
	TElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag;
    PointerTag RTag;
}  BiThrNode, *BiThrTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或者后继的线索，因此线索化的过程就是在遍历的过程中修改空指针的过程。

下面是中序遍历线索化的递归函数代码：

// 全局变量，始终指向刚刚访问过的结点
BiThrTree pre;
void InThreading(BiThrTree p){
  if(p){
    InThreading(p->lchild);
    if(!p->lchild){
      // 没有左孩子
      p->LTag = Thread;
      p->lchild = pre;
    }
    if(!p->rchild){
      // 没有右孩子
      p->RTag = Thread;
      // 指向后继，也就是当前结点p
      p->rchild = p;
    }
    // 保持 pre 指向p的前驱
    pre = p;
    InThreading(p->rchild);
  }
}

通过上述代码可以得到线索二叉树，而对它进行遍历会发现相当于是操作一个双向链表一样。同样是在二叉线索链表上添加一个头结点，如下图所示：

这里令二叉树的中序序列中的第一个结点H的左指针和最后一个结点G的右指针指向头结点，令头结点的左指针指向根结点，右指针指向结点G。这样做的好处是我们既可以从第一个结点开始顺其后继进行遍历，也可以从最后一个结点开始顺前驱进行遍历。

遍历的代码如下：

bool InOrderTraverse_Thr(BiThrTree T){
  BiThrTree p;
  // p 指向根结点
  p = T->lchild;
  while(p != T){
    // 空树或者遍历结束时，p == T
    while(p->LTag == Link)
      // 循环到中序遍历序列的第一个结点
      p = p->lchild;
    // 显示结点数据，也可以实现其他操作
    printf("%c", p->data);
    while(p->RTag == Thread && p->rchild != T){
      // 根据线索，寻找后继结点，并输出数值或者进行其他操作
      p = p->rchild;
      printf("%c", p->data);
    }
    // p 指向当前结点的右孩子，暂时结束了根据线索来寻找后继结点
    p = p->rchild;
  }
  return true;
}

线索二叉链表的存储结构适用于如果所用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继。

树、森林与二叉树的转换

树转换为二叉树

树转换为二叉树的步骤如下：

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

上述步骤可以如下图所示一样：

森林转换为二叉树

步骤如下：

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

下图就是一个森林转为二叉树的例子。

二叉树转换为树

二叉树转为树是树转为二叉树的逆过程，具体步骤如下：

加线。若某结点的左孩子存在，则将其左孩子的所有右孩子结点都与当前结点连接起来。
去线。删除原来二叉树中所有结点与其右孩子结点的连线。
层次调整。使之结构层次分明。

下图是一个例子。

二叉树转为森林

判断一棵二叉树能够转为森林还是一棵树的方法很简单，就是看其根结点是否有右孩子，如果有就是森林，没有就是一棵树。

转换为森林的步骤如下：

从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除，如此重复，直到所有右孩子连线都删除为止，得到分离后的二叉树。
将所有二叉树转为树即可。

下图是一个例子。

树与森林的遍历

最后是介绍树和森林的遍历问题。

树的遍历

树的遍历分为两种方式：

先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树。
后根遍历，即先依次后根遍历每棵子树，然后再访问根结点。

如对下图的树，它的先根遍历序列是ABEFCDG，后根遍历序列是EFBCGDA。

森林的遍历

森林的遍历也是分两种：

前序遍历：先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。比如对于上述二叉树转为森林的例子中最后得到的三棵树的森林，前序遍历的序列是ABCDEFGHJI。
后序遍历：是先访问森林中的第一棵树，然后用后根遍历的方法遍历每一棵子树，然后再访问根结点，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。同样还是刚才的例子，后根遍历的序列是BCDAFEJHIG。

对照上述例子中的二叉树的前序和中序遍历结果可以发现，森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。同时，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

赫夫曼树

定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树(Huffman Tree)。赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

假设有$n$个权值，则构造出的赫夫曼树有$n$个叶子结点。 n个权值分别设为 $w_1,w_2,\ldots,w_n$，则赫夫曼树的构造规则为：

将$w_1,w_2,\ldots,w_n$看成是有$n$ 棵树的森林(每棵树仅有一个结点)；
在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
从森林中删除选取的两棵树，并将新树加入森林；
重复2、3步，直到森林中只剩一棵树为止，该树即为所求得的赫夫曼树。

赫夫曼树的性质有：

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL
赫夫曼树的形状是不唯一的，但是它的带权路径长度WPL是唯一的。*

小结

这部分内容是之前看《数据结构算法与应用：C++语言描述》时没有记录到的知识点，但是在做有关树的练习题的时候却有涉及到，比如线索二叉树和赫夫曼树，特别是后者，一般会考察如何构造赫夫曼树以及求其带权路径长度。刚好在《大话数据结构》中看到，就做下笔记，总结下。