【数据结构】树和森林的相互转换及哈夫曼树

1. 树和二叉树的转换

孩子兄弟表示法

在树和二叉树的转化过程中，我们将第一个孩子看做左指针，将下一个孩子看做右指针。

// 树的存储——孩子兄弟表示法
typedef struct CSNode{
    ElemType data;    //  数据域
    struct CSNode *firstchild,*nextsibling;  // 第一个孩子和右兄弟指针
}CSNode,*CSTree;

2. 森林和二叉树转换

我们将树的各个根结点视为兄弟结点，即可转换为二叉树的形式。

3. 哈夫曼树

1. 带权路径长度

结点的权：有某种现实含义的数值（如：表示结点的重要性等）

结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该节点上权值的乘积。

树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL,Weighted Path Length）

2. 哈夫曼树的定义

在含有n个带权叶结点的二叉树中，其中带权路径（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。

3. 哈夫曼树的构造

给定n个权值分别为w1,w2,……wn的结点，构造哈夫曼树的算法描述如下：

1. 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
2. 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树根结点的权值之和。
3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
4. 重复步骤2和3，直至F中只剩下一棵树为止。

特点：

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
2. 哈夫曼树的结点总数为2n-1。
3. 哈夫曼树中不存在度为1的结点。
4. 哈夫曼树并不唯一，但WPL必然相同且为最优。

4. 哈夫曼编码

固定长度编码：每个字符用相等长度的二进制位表示。

可变长度编码：允许对不同字符使用不等长的二进制位表示。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

由哈夫曼树得到哈夫曼编码：字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前的方法构造哈夫曼树。

哈夫曼树不唯一，因此哈夫曼编码也不唯一。

哈夫曼编码可用于数据压缩。