为什么要对二叉树进行线索化？
对二叉树进行遍历是以一定的规则将二叉树的节点排列成一个线性序列,这些线性序列有且仅有一个直接前驱和直接后继,
但是以二叉链表进行存储的时候，只能找到节点的左右孩子信息，不能直接得到节点在任一序列的前驱和后继信息
前驱和后继信息只能在遍历的动态过程中才能得到。
如何获取到前驱和后继的信息呢？
在有n个节点的二叉链表中必定存在n+1个空链域，利用这些空链域存放节点的前驱和后继信息,
所以在每个节点上增加两个指针域分别指向节点在任一序列中的前驱和后继信息。
线索二叉树的结点结构：
代码如下：
typedef struct ThreadNode {
ElemType data;
struct ThreadNode* lchild, * rchild;
int leftTag, RightTag; //一般简写成ltag和rtag，左右搜索的标志
};
//中序遍历二叉树，一边遍历一遍线索化
void InThread(ThreadTree T) {
if (T != NULL) {
InThread(T->lchild);//中序遍历左子树
visit(T); //访问根结点
InThread(T->rchild);//中序遍历右子树
}
}
void visit(ThreadNode* q) {
if (q->lchild == NULL) {//左子树为空，建立前驱线索
q->lchild = pre;
q->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = q; //建立前驱结点的后继线索
pre->rtag = 1;
}
pre = q;
}
ThreadNode* p = NULL; //全局变量pre 指向当前结点
*线索化二叉树需要对最后一个结点进行处理：
void CreateInThread(ThreadTree T）{
pre = NULL; //pre初始指向NULL
if (T!= NULL) { //非空二叉树才能进行线索化
InThread(T); //中序遍历线索化二叉树
if (pre->rchild == NULL)
pre->rtag = 1; //处理遍历的最后一个结点
}
}
ThreadNode* p = NULL;
与中序线索化二叉树不同的是需要避免指针指向的问题
与中序线索化相比只需多下面这步：
void PreThread(ThreadTree T) {
if (T != NULL) {
visit(T);
if (T->ltag == 0) //特殊处理，当lchild不是前驱线索
PreThread(T->lchild);//前序遍历左子树
PreThread(T->rchild);//前序遍历右子树
}
}
定义:给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树.
哈夫曼树相关的几个名词
路径 ：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。
路径长度 ：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，
那么从根结点到第 i 层结点的路>径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。
结点的权 ：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。
结点的带权路径长度 ：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10
树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为：
WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。
在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。
对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
1.在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
2.在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
3.重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
图 2 中，（A）给定了四个结点a，b，c，d，权值分别为7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是哈夫曼树。
构建哈夫曼树时，首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根，所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始，根据需求遍历树中的结点，因此每个结点需要有指向其左孩子和右孩子的指针。
所以，哈夫曼树中结点构成用代码表示为：
//哈夫曼树结点结构
typedef struct {
int weight;//结点权重
int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
}HTNode, *HuffmanTree;
构建哈夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。
查找权重值最小的两个结点的思想是：从树组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：
(1)如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
(2)如果介于两个结点权重值之间，替换原来较大的结点；
实现代码：
//HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
void Select(HuffmanTree HT, int end, int *s1, int *s2)
{
int min1, min2;
//遍历数组初始下标为 1
int i = 1;
//找到还没构建树的结点
while(HT[i].parent != 0 && i <= end){
i++;
}
min1 = HT[i].weight;
*s1 = i;
i++;
while(HT[i].parent != 0 && i <= end){
i++;
}
//对找到的两个结点比较大小，min2为大的，min1为小的
if(HT[i].weight < min1){
min2 = min1;
*s2 = *s1;
min1 = HT[i].weight;
*s1 = i;
}else{
min2 = HT[i].weight;
*s2 = i;
}
//两个结点和后续的所有未构建成树的结点做比较
for(int j=i+1; j <= end; j++)
{
//如果有父结点，直接跳过，进行下一个
if(HT[j].parent != 0){
continue;
}
//如果比最小的还小，将min2=min1，min1赋值新的结点的下标
if(HT[j].weight < min1){
min2 = min1;
min1 = HT[j].weight;
*s2 = *s1;
*s1 = j;
}
//如果介于两者之间，min2赋值为新的结点的位置下标
else if(HT[j].weight >= min1 && HT[j].weight < min2){
min2 = HT[j].weight;
*s2 = j;
}
}
}
注意：s1和s2传入的是实参的地址，所以函数运行完成后，实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置。
原文：https://www.cnblogs.com/Jiegeboke/p/14721498.html