系列文章目录

目录

• 树和森林的遍历
• • 树的遍历
  • 森林的遍历
  • 基本算法
  • • 递归先根遍历树
    • 迭代先根遍历树
    • 树和森林的层次遍历
• 压缩与哈夫曼树
• • 文件编码
  • 扩充二叉树
  • • 哈夫曼树和哈夫曼编码
    • • 哈夫曼树的基本思路
      • 哈夫曼编码

---

树和森林的遍历

树的遍历

• 先根遍历：先访问树的根结点，然后依次先根遍历每颗子树
• 后根遍历：先依次后根遍历每颗子树，然后访问树的根结点

森林的遍历

• 先根遍历森林：
  • 访问森林中第一棵树的根节点
  • 先根遍历第一棵树中的诸子树
  • 先根遍历其余的诸树（森林）

森林的先根遍历与其对应的二叉树先根遍历相同

• 后根遍历森林：
  • 后根遍历第一棵树的诸子树
  • 访问森林中第一棵树的根节点
  • 后根遍历其余诸树（森林）

森林的后根遍历序列与其对应的二叉树的中根遍历序列一致

基本算法

递归先根遍历树

PreOrder(t)
{if t == NULL return;print(Data(t));GFC(t,child); // 找到t的第一个子节点while chile != NULL{PreOrder(child);GNB(child,child);}
}

迭代先根遍历树

思路
（1）若结点p不为空，访问结点p，将结点p压入栈，并将其大儿子结点设为结点p；反复执行(1)，直至结点p为空
（2）从栈中弹出一个结点，将其设为结点p，若它有大兄弟结点,则将其大兄弟结点压入栈，且将该兄弟结点设为结点p；否则，反复执行(2)，直
至弹出的结点有大兄弟结点或栈空以至无结点可弹出
（3）反复执行(1)和(2)，直至栈为空

伪代码

NPO(t)
{create(s);p = t;bool flag = True;while flag or S非空{flag = False;while p != NULL;{print(Data(p));Push(S,p);p = FierstChlid(p)}while p != NULL and S 非空;Pop(S,p);p = NextBrother}
}

树和森林的层次遍历

LevelOrder(t)
{CREATE(Q);Q = t;	// 根节点入队列while not IsEmpty(Q){p = Q;while p != NULL{print(Data(p));if FirstChild(p) != NULL  Q = FirstChild(p);p = NextBrother(p);}}
}

压缩与哈夫曼树

文件编码

• 假设有一个文件仅包含7种字符：a、e、i、s、t、sp(空格)和nl(换行)，且文件中有10个a，15个e，12个i，3个s，4个t，13个sp，1个nl

• 因为「${\log }_{2}7$]=3，所以，每个字符都至少由一个3位的二进制串表示。于是文件的总位数至少应该是：10×3+15×3+12×3+3×3+4×3+13×3+1×3=174

• 在实际应用的一些大文件中，字符被使用的比率是非平均的，即有些字符出现的次数较多，而有些字符出现的次数却非常少。
  如果所有字符都由等长的二进制码表示,将会造成空间浪费

• 如何才能减少不必要的空间浪费

• 文件压缩的通常策略:采用不等长的二进制码，令文件中出现频率高的字符的编码尽可能短

  • 采用不等长编码又可能会产生多义性。例如：如果用01表示a，10表示b，1001表示c，那么对于编码1001，我们无法确定它表示字符c，还是表示字符串ba，其原因是b的编码与c的编码的开头(前缀)部分相同
  • 为避免出现多义性,必须要求字符集中任何字符的编码都不是其它字符的编码的前缀,满足这个条件的编码被称为前缀码。显然,等长编码是前缀码

• 怎样的前缀码才能使文件的总编码长度最短

  • 设组成文件的字符集A={a1,a2,…,an}，其中，a的编码长度为$I_i$；a出现的次数为$c_i$。要使文件的总编码最短，就必须要确定$I_i$，使得取最小值
    $$\sum _{i=0}^n{c}_i{I}_i$$

• 如何设计出总编码最短的前缀码

  • 哈夫曼算法

扩充二叉树

定义
为了使问题的处理更为方便，每当原二叉树中出现空子树时，就增加特殊的结点——空树叶，由此生成的二叉树称为扩充二叉树

• 扩充二叉树中每个圆形结点都有两个子结点,每一个方形结点都没有子结点
• 规定空二叉树的扩充二叉树为只有一个方形结点。以下称圆形结点为内结点,方形结点为外结点0

• 扩充二叉数的外通路长度定义为从根到每个外结点的路径长度之和，内通路长度定义为从根到每个结点的路径长度之和

• 给扩充二叉树的n个外结点分别赋上一个实数权。扩充二叉树的加权外通路长度定义为:
  $$WPL=\sum _{i=0}^n{w}_i{L}_i$$
  其中n表示外结点的个数，$w_i$和$L_i$分别表示外结点$k_i$的权值和根到$k_i$的路径长度

• 在外结点权值分别为$w_0,w_1,...,w_{n-1}$的所有扩充二叉树中，加权外通路长度最小的扩充二叉树称为最优二叉树‘

哈夫曼树和哈夫曼编码

• 文件编码问题就变成构造最优二叉树问题,每个外结点代表一个字符，其权值代表该字符的频率,从根到外结点的路径长度就是该字符的编码长度
• 为求得最优二叉树,哈夫曼巧妙的设计了哈夫曼算法,通过哈夫曼算法可以建立一棵哈夫曼树,从而为压缩文本文件建立了哈夫曼编码

哈夫曼树的基本思路

1. 根据给定的n个权值$w_1$,$w_2$,…,$w_n$构成n棵二叉树的森林F={$T_1,T_2,\dots ,T_n$},其中每棵二叉树$T_i$中都只有一个权值为$w_i$的根结点,其左、右子树均为空
2. 在森林F中选出两棵根结点权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和
3. 从F中删除构成新树的那两棵树,同时把新树加入F中
4. 重复第2和第3步,直到F中只含有一棵树为止,此树便是哈夫曼树

例子

哈夫曼编码

将哈夫曼树每个分支结点的左分支标上0，右分支标上1，把从根结点到每个叶结点的路径上的标号连接起来，作为该叶结点所代表字符的编码，这样得到的编码称为哈夫曼编码

• 定理：在外结点权值分别为$w_0,w_1,\dots ,w_{n-1}$的扩充二叉树中，由哈夫曼算法构造出的哈夫曼树的带权路径长度最小,因此哈夫曼为最优二叉树
• 根据该定理可知，对于所有的编码，哈夫曼编码使文件的总编码长度最短。实际上，哈夫曼算法的应用广，这里只是以哈夫曼编码为例来说明哈夫曼算法。由观察可知，字符集中的字符所在的结点均是哈夫曼树中的外结点
• 哈夫曼树中没有度为1的结点

示例

在构造哈夫曼树的过程中，没有一片树叶是其他树叶的祖先，所以每个叶结点对应的编码不可能是其他叶结点对应的编码前缀。由此可知哈夫曼编码是二进制的前缀码

哈夫曼树中每个结点的结构

其中，LLINK和RLINK为链接域，INFO为信息域，Weight为全值

伪代码

Huffman(H,m,t)
{for (i = 1; i<=m;i++){LLINK(H[i]) = RLINK(H[i]);RLINK(H[i]) = NULL;}for (i = 1,i<m;i++){t = new;P1 = H[i];P2 = H[i+1];Weight(t) = Weight(P1) + Weight(P2);LLINK(t) = P1;RLINK(t) = P2;}j = i+2;while (Weight(t)>Weight(H[j])){H[j-1] = H[j];j = j+1;H[j-1] = t;}
}