携手创造，共同生长！这是我参与「日新方案 · 8 月更文挑战」的第22天，点击查看活动详情

头绪化二叉树的认识

空链域的呈现

• 对于具有n个节点的二叉树，选用链式存储结构时，每个节点有两个指针域，总共有2n个指针域
• 一起又由于只要n-1个节点被有用指针所指向（只要根节点没有被指向）
• 所以共有2n-(n-1)=n+1个空链域

头绪：
咱们知道遍历二叉树的成果是一个节点的线性序列，所以能够运用上面的空链域来存储指向节点的前驱节点和后继节点，这样的指向该线性序列中的前驱节点和后继节点的指针，称为头绪。

头绪二叉树
每个节点加上头绪的二叉树叫做头绪二叉树

规则：

• 当某节点的左指针为空时，就令该指针指向按某种方法遍历二叉树时得到的该节点的前驱节点
• 当某节点的右指针为空时，就令该指针指向按某种方法遍历二叉树时得到的该节点的后继节点

存储结构：

在节点的存储结构中增加两个标志位来区分左指针指向的节点到底是左孩子节点仍是前驱节点，右指针同理

左标志ltag:

• ltag == 0 表明lchild指向左孩子节点
• ltag == 1 表明lchild指向前驱节点

右标志rtag:

• rtag == 0 表明lchild指向右孩子节点
• rtag == 1 表明lchild指向后继节点

优缺陷：

优点：

• 进步运用率，运用了被糟蹋的n+1个空链域
• 进步遍历速度，寄存头绪，能够便利的查找前驱节点和后继节点

缺陷：

• 节点的刺进和删除费事，且速度也比较慢
• 头绪子树不能共用

二叉树的头绪化

对一个二叉树以某种方法遍历使其变为头绪二叉树的进程就叫做二叉树的头绪化

进程：

1. 检查当时节点的左、右指针域是否为空
2. 如果为空，将他们改为指向前驱节点或后继节点
3. 创立一个头节点，并树立头节点和根节点之间的头绪

头绪化二叉树的遍历

介绍

遍历某种次序的头绪二叉树，便是从该次序下的开端节点出发，找到当时节点在该次序下的后继节点，直到终端节点。

注：查找先序/后序前驱节点有必要要知道该节点的双亲节点，而二叉链表中没有寄存指向双亲的指针，因此实际运用中很少用到先序/后序头绪二叉树，下面运用的是 中序头绪二叉树分析

哈夫曼树的介绍

带权途径长度： 在许多应用中，常常将树中的节点赋上一个有某种意义的数值，称此数值为该节点的权，从树根节点到某节点之间的途径长度与该节点上权值的乘积称为该节点的带权途径长度。

WPL： 树中所有叶子节点的带权途径长度之和称为该树的带权途径长度，记为WPL

在n个带权叶子节点构成的所有二叉树中，带权途径长度WPL最小的二叉树称为哈夫曼树。

带权途径长度核算
1、WPL = 1 * 2 + 3 * 2 + 5 * 2 + 7 * 2 = 32
2、WPL = 1 * 2 + 3 * 3 + 5 * 3 + 7 * 1 = 33
3、WPL = 7 * 3 + 5 * 3 + 5 * 2 + 1 * 1 = 43
4、WPL = 1 * 3 + 3 * 3 + 5 * 3 + 7 * 1 = 29

经过核算发现第四个二叉树是哈夫曼树

能够具有确认权值的叶子节点能够结构出多个具有不同带权途径长度的二叉树，其中值最小的二叉树叫做哈夫曼树，这里第四个二叉树便是哈夫曼树

哈夫曼树的结构

给定n个权值，怎么结构一棵含有n个给定权值的叶子节点的二叉树，使其带权途径长度WPL最小呢？

1、先将这n个权值作为带权值的根节点，左右子树均为空

2、选取权值最小的两颗树，别离作为左右子树结构一棵新的二叉树，其根节点的权值为左右子树根节点的权值之和

3、重复2步骤，直到把所有的节点都放到树上

留意：

• 之前给定的权值，全都在叶子节点上，分支节点有必要是叶子节点核算出来的成果
• 权值越小的节点所在的层次越深

哈夫曼树的节点

{
char data;//节点值
double weight;//权重
int parent;//双亲节点
int lchild;//左孩子节点
int rchild;//右孩子节点
}

阐明：

• 为了便利的结构双亲节点，所以需要保存双亲节点
• 为了核算权值，还需要加上本节点的权重信息

哈夫曼编码

来历：

在数据通信中，经常需要将传送的文字转换为二进制字符0和1组成的字符串，这个进程称为编码，明显，咱们希望电文编码的代码长度最短，而经过哈夫曼树能够把电文编码的代码长度结构为最短。

本质： 哈夫曼编码的本质便是运用频率越高的字符选用越短的编码

结构方法：

• 规定哈夫曼树中的左节点为0，右节点为1，
• 则从根节点到每个叶子节点所经过的分支对应的0和1组成的序列便为该节点对应字符的编码
• 这种编码方法便是哈夫曼编码

编码作用：

• 呈现次数较多的字符处于树的上方，这个字符的编码程度就短
• 而且呈现次数较多的元素编码长度短，呈现次数较多的元素编码长度长，能够起到紧缩作用
  • 由于能够根据编码长度来进行存储，而不是直接拓荒最大的存储空间
  • 这样当有些字符并不需要这么大空间的时分就引起了糟蹋

优点：

• 避免糟蹋空间，起到紧缩作用，由于能够根据编码长度的大小来确认存储空间
• 解决多义性问题，由于所有的叶子节点都是唯一的

总结：

• 哈夫曼树便是所有叶子节点的带权途径最小的树，也叫做最优二叉树
• 结构哈夫曼树的原理便是将权值最小的叶子节点放在最深层，权值越高的层级越小
• 哈夫曼编码能够将运用频率越高的字符选用越短的编码
• 具体做法便是将左节点作为0，右节点作为1，进行哈夫曼树结构