数据结构与算法（十一）——线索化二叉树&哈夫曼树
一、线索化二叉树
1，产生的背景
如上图所示，是一个二叉树。可以看到，每一个节点都有三个元素：左子指针域、右子指针域、值域。对于存在左右子树的节点，其左右指针域指向的分别是各自的左右子节点；而对于未存在左子树，或者未存在右子树，或者左右子树均未存在的节点，该节点的左子指针域、右子指针域、左右指针域就会指向为空，此时就会存在指针域空间浪费的情况。而线索化二叉树就可以将这些浪费的指针域空间给利用起来，这是第一个背景。
第二个背景就是，可以更加快速和便捷地查找到某个节点的前驱和后继节点。
2，对二叉树进行线索化的逻辑
二叉树的线索化，实际上就是将某个节点的未利用到的指针域空间指向某种遍历次序（前序、中序、后序）下的前驱或者后继节点。如下图所示，实线指向的就是子节点，虚线指向的就是前驱结点或者后序节点：
需要注意的是，前驱或者后继的指向是跟遍历次序有关的，某一个节点的前驱和后继在不同的遍历次序下是不一样的。比如，在前序、中序以及后序遍历的次序下，某个节点的前驱或者后继的指向都是不一样的。
与一般的二叉树相比，线索化的二叉树无非就是将空余的指针域给利用了起来，然后将这些空余的指针域指向某种遍历次序下的前驱或者后继。线索化的目的其实就是为了能够快速找到某一个节点的前驱和后继节点。
并不是所有的二叉树节点都可以线索化的，只有当前节点的左子节点或者右子节点为空的时候，当前节点才可以被线索化。若某节点的左子树为空，则该节点的左子指针域指向前驱节点；若某节点的右子树为空，则该节点的右子指针域指向后继节点。
如上图所示，是中序遍历次序下的二叉树中各个前驱后继指针的指向。实际上，我们在对二叉树进行线索化的时候，肯定是需要进行一次遍历的，分析遍历到的每一个节点，如果有无用的指针域，那么就为其设置前驱或者后继。
3，如何判断某节点的左子节点指针指向的是左子节点还是前驱结点
线索化之后，二叉树的某一个节点的左子指针域和右子指针域就都指向了某一个节点，那么我们该如何区分左子指针域指向的是该节点的左子节点还是前驱结点呢？
可以通过在节点结构中加一个左标识（右标识）来判断左子指针域（右子指针域）指向的是左子节点（右子节点）还是前驱节点（后继节点）。
如下图所示，就是加了标识位的线索化了的二叉树：
可以看到，此时的节点结构中包含五个元素：值域、左右子节点指针域、左右子节点指针类型。
4，代码
（1）二叉树的结构
#include <stdio.h>
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
// 操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 指针域指向的类型
typedef enum : int {
link, // 左子节点、右子节点
thread, // 线索化，前驱节点、后继节点
} PointerType;
// 节点值的类型
typedef char ElementValueType;
#define Nil '#' // 定义元素的空值
// 节点构造
typedef struct BinaryTreeNode {
// 值域
ElementValueType data;
// 指针域
struct BinaryTreeNode *leftChild;
struct BinaryTreeNode *rightChild;
// 指针域类型
PointerType leftChildType;
PointerType rightChildType;
} BinaryTreeNode;
// 二叉树类型
typedef struct BinaryTreeNode * BinaryTree;（2）二叉树的构造
// 1，二叉树的构造
char *initialString = "ABDH##I##EJ###CF##G##";
int initialIndex = 0;
void createBinaryTree(BinaryTree *tree) {
// 递归结束条件
ElementValueType currentValue = initialString[initialIndex];
if (currentValue == Nil) { // 当前节点值为空值
return;
}
// 为当前节点开辟空间
*tree = malloc(sizeof(BinaryTreeNode));
// 给当前节点值域赋值
(*tree)->data = initialString[initialIndex++];
// 递归构造左子节点
createBinaryTree(&((*tree)->leftChild));
(*tree)->leftChildType = (*tree)->leftChild ? link : thread;
// 递归构造右子节点
createBinaryTree(&((*tree)->rightChild));
(*tree)->rightChildType = (*tree)->rightChild ? link : thread;
}（3）二叉树的线索化
我们这里采用中序遍历的次序进行线索化。
使用preNode来记录当前遍历到的节点的上一个节点。
// 2，中序遍历二叉树，将其线索化
struct BinaryTreeNode *preNode;
void threadBinaryTree(BinaryTree *tree) {
// 递归结束的条件
if (!(*tree)) {
return;
}
// 处理左子树
threadBinaryTree(&((*tree)->leftChild));
// 左子节点指针域
if (!(*tree)->leftChild) {
// 前驱结点
(*tree)->leftChild = preNode;
(*tree)->leftChildType = thread;
} else {
(*tree)->leftChildType = link;
}
// 前驱节点的右子节点指针域
if (preNode && !preNode->rightChild) {
preNode->rightChild = *tree;
preNode->rightChildType = thread;
} else if (preNode) {
preNode->rightChildType = link;
}
// 更新上一个节点
preNode = *tree;
// 处理右子树
threadBinaryTree(&((*tree)->rightChild));
}（4）中序遍历二叉树，将其循环线索化
上面👆第（3）步中线索化好了的二叉树，在遍历的时候，实际上就类似于去操作一个双向链表结构。此时我们可以考虑一下，将这个“双向链表”优化成“双向循环链表”，也就是说，我们可以在二叉树根节点的头上再增加一个头结点。关于这个头结点相关的各个指针指向，说明如下：
- ①头结点的左子节点设置为二叉树的根节点
- ②头结点的右子节点指针线索化指向为二叉树的最后一个叶子节点
- ③二叉树的第一个遍历到的节点的左子节点指针线索化为头结点
- ④二叉树的最后一个叶子节点指针线索化为头结点
图示如下：
这样做的一个好处就是，我可以从第一个节点开始沿着后继节点进行遍历，也可以从最后一个节点开始沿着前驱节点进行遍历。
代码如下：
// 3，中序遍历二叉树，将其循环线索化
void circleThreadBinaryTree(BinaryTree *circleThreadedTree, BinaryTree *tree) {
// 创建头结点
*circleThreadedTree = malloc(sizeof(BinaryTreeNode));
// 头结点的左子节点设置为根节点
(*circleThreadedTree)->leftChild = *tree;
(*circleThreadedTree)->leftChildType = link;
// 在线索化二叉树之前设置preNode的初始值，以将二叉树的第一个遍历到的节点的前驱设置为叶子节点
preNode = *circleThreadedTree;
// 对二叉树进行线索化
threadBinaryTree(tree);
// 头结点的右子节点线索化为二叉树的最后一个叶子节点
(*circleThreadedTree)->rightChild = preNode;
(*circleThreadedTree)->rightChildType = thread;
// 二叉树的最后一个叶子节点的后继设置为头结点
preNode->rightChild = *circleThreadedTree;
preNode->rightChildType = thread;
}（5）遍历循环线索化之后的二叉树
之前我们在遍历未经线索化的二叉树的时候，使用的是递归操作；二叉树经过线索化之后，再对其进行遍历就没必要使用递归了，而是直接通过后继节点和前驱节点进行迭代就可以了。
代码如下：
// 4，遍历线索化后的二叉树
void printBinaryNodeValue(ElementValueType element) {
printf("%d", element);
}
void traverseCircleThreadedBinaryTree(BinaryTree tree) {
struct BinaryTreeNode *tempNode = tree->leftChild; // 一开始指向根节点，自根节点开始遍历
while (tempNode != tree) { // 经过一轮遍历之后最终会重新回到头结点，此时结束遍历
// 找到当前未遍历到的最前面的节点
while (tempNode->leftChildType == link) {
tempNode = tempNode->leftChild;
}
// 打印当前节点信息
printBinaryNodeValue(tempNode->data);
// 通过后继指针依次找到接下来的节点
while (tempNode->rightChildType == thread && tempNode->rightChild != tree) { // 有后继节点的时候则打印后继节点
tempNode = tempNode->rightChild;
printBinaryNodeValue(tempNode->data);
}
// 有右子节点的时候，则进行新一轮遍历
tempNode = tempNode->rightChild;
}
}逻辑思路图示如下：
二、哈夫曼树 & 哈夫曼编码
哈夫曼树，又称为最优二叉树，是一种带权路径长度最短的二叉树。
哈夫曼编码是一种用于无损数据压缩的权编码算法。
1，哈夫曼树的必要性
如上图所示，学生分五类：优秀（90~100）、良好（80~90）、中等（70~80）、及格（60~70）、不及格（60分以下），这里我是按照成绩依次递增的顺序进行条件判断的。各个成绩区间的学生比例分布如下：
可以看到，有70%的学生是位于70~90的分数区间之内，但这些学生需要经历3~4次判断才可以确定其最终成绩，这样就会多出来很多初期的判断。如果数据量很大，那么就会造成效率问题。接下来我们就将树的路径长度作为指标来分析一下该效率问题。
节点的路径长度指的是，从根节点到该节点的路径上所包括的边的数目。
树的路径长度指的是，该树中所有节点的路径长度之和。
如上图所示，节点D的路径长度是4。
上面二叉树的路径长度是1+1+2+2+3+3+4+4=20。
接下来我按照权重占比，来调整一下条件判断的次序，如下图所示：
此时，占比较高的良好（D）和中等（C）的路径长度都是2，而不是之前的4和3了。
再计算一下二叉树的路径长度，是1+1+2+2+2+2+3+3=16。
可以看到，根据权重占比对二叉树进行改造之后，占比较高的节点的路径长度就变小了。
上面👆我只是计算了二叉树改造前后的路径长度，该路径长度并没有将权重计算进去，此时我们是没有办法据此来判断一个树的效率高低的。接下来我们就来计算一下WPL（Weighted Path Length of Tree），即树的带权重的路径长度，它是树的所有叶子节点的带权路径长度之和，它是可以判断树的效率高低的。
首先来看一下改造之前的树的WPL：
一定要注意哦，一棵树的WPL指的是该树所有的叶子节点的加权路径长度之和。因此这里的WPL=315。
接下来再看一下根据权重改造之后的二叉树的WPL：
可以看到，按权重改造优化之后，树的WPL变为了220，对比之前的350，说明效率大大提高了。
2，哈夫曼树的构建思路
假设A、B、C、D、E五个节点的权重值分别是5、15、40、30、10，那么如何来构建一个哈夫曼树呢？
首先，取出两个最小权重节点A和E，小的放左边，大的放右边，并将这俩节点的值相加构建一个新的节点N1：
此时N1的权重值是15。
然后找到剩余节点中权重最小的节点B，此时发现N1和B节点的权重值都是15，所以将B节点放到N1节点的右侧，并生成一个新的节点N2：
此时，N2的权重值是30。
然后找到剩余节点中权重最小的节点D，此时发现N2和D节点的权重值都是30，所以将D节点放到N2节点的右侧，并生成一个新的节点N3：
此时，N3节点的权重值是60。
然后找到剩余节点中权重最小的节点C，其权重值是40，比N3的权重值60要小，所以将C节点放到N3节点的左侧，并生成一个新的节点T：
这里的T节点就是该哈夫曼树的根节点。
此时该树的加权路径长度WPL为40*1+30*2+15*3+5*4+10*4=205。
3，哈夫曼编码思考
现在需要将26个英文字母转换成二进制，假设A是000，后面依次累加，则ABCDEFG…转换成二进制如下：
000 001 010 011 100 101 110……按照这样的规则，字符串BADCADFEED转换成二进制为：
001 000 011 010 000 011 101 100 100 011接下来我们看一下如何对这些英文字母进行哈夫曼编码。
我们知道，在英文语境中，肯定有一些字母是出现频率比较高的，有些是出现频率比较低的。这里我们假设ABCDEF的权重分别为27、8、15、15、30、5，如下：
接下来我按照权重对这些字母进行排序，如下：
然后我们就可以按照权重来构建一个哈夫曼树。
首先找到权重最小的两个节点F和B，权重较小的F放在左边，二者生成一个父节点N1，如下：
此时N1的权重值是13。
接下来找到剩余节点中权重最小的那一个C节点，其权重是15，比N1的权重13要大，所以放在N1的右边，如下图所示：
N2是N1和C的双亲节点，其权重值是28。
接着找到余下来的权重最小的节点D，其权重值是15。这里的这个D放在哪里呢，是放在节点N2的右侧吗？不要这样想当然哦~此时需要重新再构建一个子树，与当前权重倒数第二小的节点A(27)分别作为左右子节点，然后生成一个双亲结点N3，如下图所示：
此时，N3的权重值是42，N2的权重值是28。
现在还剩最后一个节点E，其权重值是30，30比28大比42小，所以将节点E放在N2的右侧，并且生成双亲结点N4：
此时，N3的权重值是42，N4的权重值是58。
最后，以N3、N4分别作为左、右子节点，生成一个双亲结点T：
这里的T就是哈夫曼二叉树的根节点，至此，一个哈夫曼二叉树就构建出来了。
可以看到，在哈夫曼二叉树中，很重要的一个原则就是保证左右子树的权重平衡。
好，现在已经生成了一个哈夫曼二叉树，接下来我将二叉树中所有的左子树路径全部标记为0，所有的右子树路径全部标记为1，如下图所示：
这样的话，ABCDEF的二进制表示如下：
A——01
B——1001
C——101
D——00
E——11
F——1000然后我们在比较一下BADCADFEED这个字符串的纯二进制表示和哈弗曼编码表示：
可以看到，使用哈夫曼编码表示比使用纯二进制表示要节省了5个字符空间。
4，哈夫曼树的构建代码
#include <stdio.h>
#include "string.h"
#include "stdlib.h"
#include <stdbool.h>
// 权重最大值
#define MaxWeight 10000
// 哈夫曼节点结构
typedef struct HaffTreeNode {
int weight; // 权重值
int parentIndex; // 父节点坐标
int leftChildIndex; // 左子节点坐标
int rightChildIndex; // 右子节点坐标
bool isAddedIntoTree; // 是否已经加入进了二叉树中
} HaffTreeNode;
// 哈夫曼树结构类型
typedef struct HaffTreeNode * HaffTree;
// 构建哈夫曼树
/*
①采用顺序存储的方式
②需要从外界传入权重数组相关信息
*/
void createHaffTree(int *weights, int weighttCount, HaffTree tree) {
// 1，首先初始化所有的节点
/*
①如果叶子节点的个数是n，则该哈夫曼树中就会有2n-1个节点
②将n个叶子节点都存放在数组的前n个位置
③将所有的叶子节点都赋予指定的权重值，所有的非叶子节点的权重值都赋值为0
④将所有节点的父节点坐标都初始化为0，子节点坐标都初始化为-1（代表没有子节点），isAddedIntoTree均设置为false代表未加入到二叉树中
*/
for (int i = 0; i < 2*weighttCount-1; i++) {
if (i < weighttCount) { // 当是叶子节点的时候
tree[i].weight = weights[i];
} else { // 当是非叶子节点的时候
tree[i].weight = 0;
}
tree[i].parentIndex = 0;
tree[i].leftChildIndex = -1; // 默认左右子节点都不存在
tree[i].rightChildIndex = -1;
tree[i].isAddedIntoTree = false; // 默认未加入到二叉树中
}
// 2，循环遍历所有节点，处理其相互关系
int theMinWeight = MaxWeight; // 最小权重值
int theSecondToTheMinWeight = MaxWeight; // 倒数第二小权重值
int indexOfMin = 0; // 最小权重的节点坐标
int indexOfSecondToMin = 0; // 倒数第二小权重的节点坐标
/*
如叶子节点有n个，则总共会有2n-1个节点，所以非叶子节点的个数为n-1
*/
for (int i = 0; i < weighttCount - 1; i++) {
// （1）寻找权重最小的俩节点
/*
寻找的区间是0~weighttCount+i之间。
一定要记住，每一次都是找到俩权重最小的节点，然后构建一个新的双亲结点并加入到节点数组中。
*/
for (int j = 0; j < weighttCount + i; j++) {
if (tree[j].weight < theMinWeight && !tree[j].isAddedIntoTree) {
theSecondToTheMinWeight = theMinWeight;
indexOfSecondToMin = indexOfMin;
theMinWeight = tree[j].weight;
indexOfMin = j;
} else if (tree[j].weight < theSecondToTheMinWeight && !tree[j].isAddedIntoTree) {
theSecondToTheMinWeight = tree[j].weight;
indexOfSecondToMin = j;
}
}
// （2）将权重最小的俩节点加入到二叉树中
/*
找到权重最小的俩节点之后，将这俩节点组合成一个小树，所以需要生成一个双亲结点，这个双亲结点就存储在节点数组的接下来的位置上。
一定要注意哦，这里的双亲结点的存储位置是我自己定义的哦，这跟我们之前说的按照层序遍历的次序进行存储是不一样的哦~
*/
// 处理俩子节点的双亲结点指针指向
tree[indexOfMin].parentIndex = weighttCount + i;
tree[indexOfSecondToMin].parentIndex = weighttCount + i;
// 将俩子节点标记为已经加入到二叉树中
tree[indexOfMin].isAddedIntoTree = true;
tree[indexOfSecondToMin].isAddedIntoTree = true;
// 给父节点权重赋值，并且设置父节点的俩子节点指针
tree[weighttCount + i].weight = tree[indexOfMin].weight + tree[indexOfSecondToMin].weight;
tree[weighttCount + i].leftChildIndex = indexOfMin;
tree[weighttCount + i].rightChildIndex = indexOfSecondToMin;
}
}5，哈夫曼编码
哈夫曼编码，指的就是通过哈夫曼树来获取编码。其代码如下：
// 哈弗曼编码的最大位数
#define MaxHaffCodeSize 100
// 哈夫曼编码结构
typedef struct HaffCode {
int bits[MaxHaffCodeSize]; // 承载哈弗曼编码的数组
int finalBitIndex; // 哈弗曼编码在bits数组中占用的结束位置
int weight; // 当前字母的权重
} HaffCode;
// 根据哈夫曼树来求出哈夫曼编码
void haffCode(HaffTree tree, int count, HaffCode *haffCodes) {
struct HaffCode *tempHaffCode = malloc(sizeof(HaffCode));
int childIndex;
int parentsIndex;
// 依次遍历各个叶子节点，以获取到每一个叶子节点的哈弗曼编码，并保存在haffCodes中
for (int i = 0; i < count; i++) {
// 1，获取当前遍历到的叶子节点的哈弗曼编码，并通过临时变量tempHaffCode来记录
tempHaffCode->finalBitIndex = 0;
tempHaffCode->weight = tree[i].weight;
childIndex = i;
parentsIndex = tree[childIndex].parentIndex;
// 自叶子节点一直遍历到根节点
while (parentsIndex != 0) {
// 左孩子节点编码为0，右孩子节点编码为1
tempHaffCode->bits[tempHaffCode->finalBitIndex] = tree[parentsIndex].leftChildIndex == childIndex ? 0 : 1;
// 将节点在二叉树中位置上移一层
tempHaffCode->finalBitIndex++;
childIndex = parentsIndex;
parentsIndex = tree[childIndex].parentIndex;
}
// 2，将临时编码变量tempHaffCode的数据赋值到haffCodes[i]中
// （1）tempHaffCode中记录的编码是逆序的，因此需要给正序过来
for (int j = 0; j < tempHaffCode->finalBitIndex - 1; j++) {
haffCodes[i].bits[j] = tempHaffCode->bits[tempHaffCode->finalBitIndex-j-1];
}
// （2）将tempHaffCode中的编码结束位置和权重赋值给haffCodes[i]
haffCodes[i].finalBitIndex = tempHaffCode->finalBitIndex;
haffCodes[i].weight = tempHaffCode->weight;
}
}以上。