如上图所示，是一个二叉树。可以看到，每一个节点都有三个元素：左子指针域、右子指针域、值域。对于存在左右子树的节点，其左右指针域指向的分别是各自的左右子节点；而对于未存在左子树，或者未存在右子树，或者左右子树均未存在的节点，该节点的左子指针域、右子指针域、左右指针域就会指向为空，此时就会存在指针域空间浪费的情况。而线索化二叉树就可以将这些浪费的指针域空间给利用起来，这是第一个背景。
第二个背景就是，可以更加快速和便捷地查找到某个节点的前驱和后继节点。
2，对二叉树进行线索化的逻辑
二叉树的线索化，实际上就是将某个节点的未利用到的指针域空间指向某种遍历次序（前序、中序、后序）下的前驱或者后继节点。如下图所示，实线指向的就是子节点，虚线指向的就是前驱结点或者后序节点：
需要注意的是，前驱或者后继的指向是跟遍历次序有关的，某一个节点的前驱和后继在不同的遍历次序下是不一样的。比如，在前序、中序以及后序遍历的次序下，某个节点的前驱或者后继的指向都是不一样的。
与一般的二叉树相比，线索化的二叉树无非就是将空余的指针域给利用了起来，然后将这些空余的指针域指向某种遍历次序下的前驱或者后继。线索化的目的其实就是为了能够快速找到某一个节点的前驱和后继节点。
并不是所有的二叉树节点都可以线索化的，只有当前节点的左子节点或者右子节点为空的时候，当前节点才可以被线索化。若某节点的左子树为空，则该节点的左子指针域指向前驱节点；若某节点的右子树为空，则该节点的右子指针域指向后继节点。
如上图所示，是中序遍历次序下的二叉树中各个前驱后继指针的指向。实际上，我们在对二叉树进行线索化的时候，肯定是需要进行一次遍历的，分析遍历到的每一个节点，如果有无用的指针域，那么就为其设置前驱或者后继。
3，如何判断某节点的左子节点指针指向的是左子节点还是前驱结点
线索化之后，二叉树的某一个节点的左子指针域和右子指针域就都指向了某一个节点，那么我们该如何区分左子指针域指向的是该节点的左子节点还是前驱结点呢？
可以通过在节点结构中加一个左标识（右标识）来判断左子指针域（右子指针域）指向的是左子节点（右子节点）还是前驱节点（后继节点）。
如下图所示，就是加了标识位的线索化了的二叉树：
可以看到，此时的节点结构中包含五个元素：值域、左右子节点指针域、左右子节点指针类型。
4，代码
（1）二叉树的结构
（2）二叉树的构造
（3）二叉树的线索化
我们这里采用中序遍历的次序进行线索化。
使用preNode来记录当前遍历到的节点的上一个节点。
（4）中序遍历二叉树，将其循环线索化
上面👆第（3）步中线索化好了的二叉树，在遍历的时候，实际上就类似于去操作一个双向链表结构。此时我们可以考虑一下，将这个“双向链表”优化成“双向循环链表”，也就是说，我们可以在二叉树根节点的头上再增加一个头结点。关于这个头结点相关的各个指针指向，说明如下：
图示如下：
这样做的一个好处就是，我可以从第一个节点开始沿着后继节点进行遍历，也可以从最后一个节点开始沿着前驱节点进行遍历。
代码如下：
（5）遍历循环线索化之后的二叉树
之前我们在遍历未经线索化的二叉树的时候，使用的是递归操作；二叉树经过线索化之后，再对其进行遍历就没必要使用递归了，而是直接通过后继节点和前驱节点进行迭代就可以了。
代码如下：
逻辑思路图示如下：
二、哈夫曼树 & 哈夫曼编码
哈夫曼树，又称为最优二叉树，是一种带权路径长度最短的二叉树。
哈夫曼编码是一种用于无损数据压缩的权编码算法。
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…转换成二进制如下：
按照这样的规则，字符串BADCADFEED转换成二进制为：
接下来我们看一下如何对这些英文字母进行哈夫曼编码。
我们知道，在英文语境中，肯定有一些字母是出现频率比较高的，有些是出现频率比较低的。这里我们假设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的二进制表示如下：
然后我们在比较一下BADCADFEED这个字符串的纯二进制表示和哈弗曼编码表示：
可以看到，使用哈夫曼编码表示比使用纯二进制表示要节省了5个字符空间。