树的存储和遍历

6.5 树与森林

本节将讨论树的存储结构、树及森林与二叉树之间的相互转换、树的遍历等。

6.5.1 树的存储结构

树的存储结构根据应用的不同而不同。

1. 双亲表示法(顺序存储结构)

#define MAX_SIZE 100
typedef struct PTNode
{ElemType data;int parent;
} PTNode;

根据该数据结构的定义，PTNode 是 “Parent Tree Node” 的缩写，即“双亲树节点”。在双亲树中，每个节点在存储自己的数据的同时，也存储了其父节点在数组中的位置。

typedef struct
{PTNode Nodes[MAX_SIZE];int root; /*  根结点位置  */int num;  /*  结点数   */
} Ptree;

图6-13所示是一棵树及其双亲表示的存储结构。这种存储结构利用了任一结点的父结点唯一的性质。可以方便地直接找到任一结点的父结点，但求结点的子结点时需要扫描整个数组。

2 孩子链表表示法

树中每个结点有多个指针域，每个指针指向其一棵子树的根结点。其实这么说有点绕口，其实就是每个指针指向

(1) 定长结点结构

指针域的数目就是树的度。

其特点是：链表结构简单，但指针域的浪费明显。结点结构如图6-14(a) 所示。在一棵有 $n$ 个结点，度为 $k$ 的树中必有 $n(k-1)+1$ 空指针域。

(2) 不定长结点结构

树中每个结点的指针域数量不同，是该结点的度，如图6-14(b) 所示。没有多余的指针域，但操作不便。

(3) 复合链表结构

$n$ 个结点的树有 $n$ 个单链表(叶子结点的孩子链表为空)，而 $n$ 个头结点又组成一个线性表且以顺序存储结构表示。

#define MAX_NODE 100
typedef struct listnode
{int childno; /*  孩子结点编号  */struct listno *next;
} CTNode; /*  表结点结构  */typedef struct
{ElemType data;CTNode *firstchild;
} HNode; /*  头结点结构  */typedef struct
{HNode nodes[MAX_NODE];int root; /*  根结点位置  */int num;  /*  结点数   */
} CLinkList;  /*  头结点结构  */

CTNode 是 “Child Next Node” 的缩写
CLinkList 是 “Child Linked List” 的缩写，即“孩子链表”。它是一种树的链式存储结构

图6-13所示的树T的孩子链表表示的存储结构如图6-16所示。

（考试可能会考，给同学们一棵树，画出若干种表示方法）

3 孩子兄弟表示法(二叉树表示法)

（最重要的表示方法，考试常考）

以二叉链表作为树的存储结构，其结点形式如图6-17(a)所示。

两个指针域：分别指向结点的第一个子结点和下一个兄弟结点。结点类型定义如下：

typedef struct CSnode
{ElemType data;struct CSnode *firstchild, *nextsibing;
} CSNode;

CSNode 是 “Child Sibling Node” 的缩写，即“孩子-兄弟节点” 。在以孩子-兄弟表示法存储树或森林时，每个节点包含一个指向它的第一个孩子节点和下一个兄弟节点的指针，称为孩子-兄弟节点。

6.5.2 森林与二叉树的转换

由于二叉树和树都可用二叉链表作为存储结构，对比各自的结点结构可以看出，以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系。

◆ 从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。
◆ 从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。

图6-18直观地展示了树和二叉树之间的对应关系。

1 树转换成二叉树

对于一般的树，可以方便地转换成一棵唯一的二叉树与之对应。将树转换成二叉树在“孩子兄弟表示法”中已给出，其详细步骤是：

• 加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。
• 去连线。除最左的第一个子结点外，父结点与所有其它子结点的连线都去掉。
• 旋转。原有的实线左斜。
• 整型。将旋转后树中的所有虚线改为实线，并向右斜。该转换过程如图6-19所示。

这样转换后的二叉树的特点是：

◆ 二叉树的根结点没有右子树，只有左子树；

◆ 左子结点仍然是原来树中相应结点的左子结点，而所有沿右链往下的右子结点均是原来树中该结点的兄弟结点。

2 二叉树转换成树

对于一棵转换后的二叉树，如何还原成原来的树? 其步骤是：

• 加虚线。若某结点 $i$ 是其父结点的左子树的根结点，则将该结点 $i$ 的右子结点以及沿右子链不断地搜索所有的右子结点，将所有这些右子结点与 $i$ 结点的父结点之间加虚线相连，如图6-20(a)所示。

• 去连线。去掉二叉树中所有父结点与其右子结点之间的连线，如图6-20(b)所示。

• 整型。将图中各结点按层次排列且将所有的虚线变成实线，如图6-20(c)所示。

3 森林转换成二叉树

当一般的树转换成二叉树后，二叉树根节点的右子树必为空。若把森林中的第二棵树(转换成二叉树后)的根结点作为第一棵树(二叉树)的根结点的兄弟结点，则可导出森林转换成二叉树的转换算法如下。

设 F = { T 1 , T 2 , ⋯ , T n } F=\{T_1, T_2,⋯,T_n\} F={T1​,T2​,⋯,Tn​} 是森林，则按以下规则可转换成一棵二叉树 $B=(\mathrm{root}，\mathrm{LB}，\mathrm{RB})$

① 若 $F=\varnothing $，则 $B$ 为空树
② 若 $F$ 非空，即 $n\ne 0$，则 $B$ 的根 $root$ 即为森林中第一棵树的根 $root(T_1)$；而其右子树 $RB$ 是从森林 F ’ = { T 2 , T 3 , ⋯ , T n } F’=\{T_2, T_3,⋯,T_n\} F’={T2​,T3​,⋯,Tn​} 转换而成的二叉树。

4 二叉树转换成森林

若 $B=(root，LB，RB)$ 是一棵二叉树，则可以将其转换成由若干棵树构成的森林： F = { T 1 , T 2 , ⋯ , T n } F=\{T_1, T_2,⋯,T_n\} F={T1​,T2​,⋯,Tn​} 。

转换算法：

① 若 $B$ 是空树，则 $F$ 为空。
② 若 $B$ 非空，则 $F$ 中第一棵树 $T_1$ 的根 $root(T_1)$ 就是二叉树的根 $root$， $T_1$ 中根结点的子森林 $F1$ 是由树 $B$ 的左子树 $LB$ 转换而成的森林；$F$ 中除 $T_1$ 外其余树组成的的森林 F ’ = { T 2 , T 3 , ⋯ , T n } F’=\{T_2, T_3,⋯,T_n\} F’={T2​,T3​,⋯,Tn​} 是由 $B$ 右子树 $RB$ 转换得到的森林。

上述转换规则是递归的，可以写出其递归算法。以下给出具体的还原步骤。

6.5.3 树和森林的遍历

1. 树的遍历

由树结构的定义可知，树的遍历有二种方法。

• 先序遍历：先访问根结点，然后依次先序遍历完每棵子树。如图6-23的树，先序遍历的次序是：
  $ABCDEFGIJHK$
• 后序遍历：先依次后序遍历完每棵子树，然后访问根结点。如图6-23的树，后序遍历的次序是：
  $CDBFIJGHEKA$

说明：
◆ 树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。
◆ 树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同。

对于一般的树而言，并没有明显的左右子树之分，因此在树上定义中序遍历并不合理。对于一般的树，我们主要考虑先遍历根节点还是遍历子树。

其实树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历逻辑上是很好理解的，根节点是没有右子树的。那么二叉树实际上逻辑理解就是，先访问根结点，然后访问他的其余子树。对于有右节点的子树的根，根左右可以理解成先访问根，然后访问根下的那棵树，最后再去访问子树森林中的其他树。这样的逻辑结果就和树的遍历中的先序遍历完全一致了。

2. 森林的遍历

设 F = { T 1 , T 2 , ⋯ , T n } F=\{T_1, T_2,⋯,T_n\} F={T1​,T2​,⋯,Tn​} 是森林，对 $F$ 的遍历有二种方法。
⑴ 先序遍历：按先序遍历树的方式依次遍历 $F$ 中的每棵树。
⑵ 中序遍历：按中序遍历树的方式依次遍历 $F$ 中的每棵树。

6.6 赫夫曼树及其应用

赫夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。

6.6.1 最优二叉树(Huffman树)

1 基本概念

① 结点路径：从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。

② 路径长度：结点路径上的分支数目称为路径长度。

③ 树的路径长度：从树根到每一个结点的路径长度之和。

例图6-23的树。$A$ 到 $F$ ：结点路径 $AEF$ ；路径长度(即边的数目) $2$ ；树的路径长度：$3\times 1+5\times 2+2\times 3=19$

④ 结点的带权路径长度：从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积。

⑤ 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记做：

$$WPL=w_1\times l_1+w_2\times l_2+\cdots +w_n\times l_n=\sum w_i\times l_i(i=1,2,\cdots ,n)$$

其中：$n$ 为叶子结点的个数；$w_i$为第 $i$ 个结点的权值； $l_i$ 为第 $i$ 个结点的路径长度。

⑥ Huffman树：具有 $n$ 个叶子结点(每个结点的权值为 $w_i$) 的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵 $WPL$ 值最小的树，称这棵树为 Huffman 树(或称最优树) 。

在许多判定问题时，利用 Huffman 树可以得到最佳判断算法。如图6-24是权值分别为 $2、3、6、7$，具有 $4$ 个叶子结点的二叉树，它们的带权路径长度分别为：

$$\begin{array}{rl}& (a)WPL=2\times 2+3\times 2+6\times 2+7\times 2=36\\ & (b)WPL=2\times 1+3\times 2+6\times 3+7\times 3=47\\ & (c)WPL=7\times 1+6\times 2+2\times 3+3\times 3=34\end{array}$$

其中(c)的 $WPL$ 值最小，可以证明是 Huffman 树。

2 Huffman树的构造

① 根据 $n$ 个权值 { w 1 , w 2 , ⋯ , w n } \{w_1, w_2, ⋯,w_n\} {w1​,w2​,⋯,wn​}，构造成 $n$ 棵二叉树的集合 F = { T 1 , T 2 , ⋯ , T n } F=\{T_1, T_2, ⋯,T_n\} F={T1​,T2​,⋯,Tn​}，其中每棵二叉树只有一个权值为 $w_i$ 的根结点，没有左、右子树；

② 在 $F$ 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左、右子树根结点的权值之和；

③ 在 $F$ 中删除这两棵树，同时将新得到的树加入F中；

④ 重复②、③，直到F只含一颗树为止。

构造 Huffman 树时，为了规范，规定 F = { T 1 , T 2 , ⋯ , T n } F=\{T_1, T_2, ⋯,T_n\} F={T1​,T2​,⋯,Tn​} 中权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树；在取值相等时，深度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。

图6-25是权值集合 W = { 8 , 3 , 4 , 6 , 5 , 5 } W=\{8, 3, 4, 6, 5, 5\} W={8,3,4,6,5,5} 构造 Huffman 树的过程。所构造的 Huffman 树的 WPL 是：

$$\mathrm{WPL}=6\times 2+3\times 3+4\times 3+8\times 2+5\times 3+5\times 3=79$$

6.6.2 赫夫曼编码及其算法

课本P147页

1. Huffman编码

在电报收发等数据通讯中，常需要将传送的文字转换成由二进制字符0、1组成的字符串来传输。为了使收发的速度提高，就要求电文编码要尽可能地短 。此外，要设计长短不等的编码，还必须保证任意字符的编码都不是另一个字符编码的前缀 ，这种编码称为前缀编码。

Huffman树可以用来构造编码长度不等且译码不产生二义性的编码。

设电文中的字符集 C = { c 1 , c 2 , ⋯ , c i , ⋯ , c n } C=\{c_1,c_2, ⋯,c_i, ⋯,c_n\} C={c1​,c2​,⋯,ci​,⋯,cn​}，各个字符出现的次数或频度集 W = { w 1 , w 2 , ⋯ , w i , ⋯ , w n } W=\{w_1,w_2, ⋯,w_i, ⋯,w_n\} W={w1​,w2​,⋯,wi​,⋯,wn​}。

从根结点到每个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结点所对应的编码，称之为 Huffman 编码。

若字符集 C = { a , b , c , d , e , f } C=\{a, b, c, d, e, f\} C={a,b,c,d,e,f} 所对应的权值集合为 W = { 8 , 3 , 4 , 6 , 5 , 5 } W=\{8, 3, 4, 6, 5, 5\} W={8,3,4,6,5,5}，如图6-25所示，则字符 $a,b,c,d,e,f$ 所对应的 Huffman 编码分别是：$10，010，011，00，110，111$。

2. Huffman编码算法实现

(1) 数据结构设计

Huffman 树中没有度为 1 的结点。若有 $n$ 个叶子结点的 Huffman 树共有 $2n-1$ 个结点，则可存储在大小为 $2n-1$ 的一维数组中。实现编码的结点结构如图6-26所示。

#define MAX_NODE 200 /*   Max_Node>2n-1  */
typedef struct
{unsigned int Weight; /*  权值域  */unsinged int Parent, Lchild, Rchild;
} HTNode，*HuffmanTree;//动态分配数组存储H树typedef char **HuffmanCode;//动态分配数组存储

(2) Huffman树的生成

算法实现

void Create_Huffman(unsigned n, HuffmanTree &HT[])
/*  创建一棵叶子结点数为n的Huffman树  */
{unsigned int w;m=2*n;int k, j;for (k = 1; k < m; k++){if (k <= n){  printf(“\n Please Input Weight : w=?”);scanf(“% d”, &w);HT[k].weight = w;} /*  输入时，所有叶子结点都有权值  */elseHT[k].weight = 0; /*  非叶子结点没有权值 */HT[k].Parent = HT[k].Lchild = HT[k].Rchild = 0;} /* 初始化Huffman树 HT */for (k = n + 1; k < m; k++){unsigned int w1 = 32767, w2 = w1;/*  w1 , w2分别保存权值最小的两个权值  */int p1 = 0, p2 = 0;/*  p1 , p2保存两个最小权值的下标  */for (j = 1; j <= k - 1; j++){if (HT[j].Parent == 0) /* 尚未合并 */{/*默认w1是最小的权值*/if (HT[j].Weight < w1){w2 = w1;p2 = p1;w1 = HT[j].Weight;p1 = j;}else if (HT[j].Weight < w2){w2 = HT[j].Weight;p2 = j;}} /*  找到权值最小的两个值及其下标  */}HT[k].Lchild = p1;HT[k].Rchild = p2;HT[k].weight = w1 + w2;HT[p1].Parent = k;HT[p2].Parent = k;}
}

说明：生成 Huffman 树后，树的根结点的下标是 $2n-1$，即 $m-1$ 。

(3) Huffman编码算法

根据出现频度(权值) Weight，对叶子结点的Huffman 编码有两种方式：
① 从叶子结点到根逆向处理，求得每个叶子结点对应字符的 Huffman 编码。
② 从根结点开始遍历整棵二叉树，求得每个叶子结点对应字符的 Huffman 编码。

算法实现

void Huff_coding(unsigned n, Hnode HT[]，Huffmancode &HC)
/*  m应为n+1,编码的最大长度n加1 */
{int k, sp, fp, m = n + 1;char *cd, *HC[m];cd = (char *)malloc(n * sizeof(char)); /*  动态分配求编码的工作空间  */cd[n] =‘\0’; /*  编码的结束标志，不加容易出乱码 */for (k = 1; k < n + 1; k++) /*  逐个求字符的编码 */{sp = n;for (p = k, fp = HT[k].parent; fp != 0; p = fp, fp = HT[p].parent)/* 在一次循环中，fp指向的是父结点，p 指向的是当前结点*//*   从叶子结点到根逆向求编码  */if (HT[fp].parent == p)cd[--sp] =‘0’;elsecd[--sp] =‘1’;HC[k] = (char *)malloc((n - sp) * sizeof(char));/*  为第k个字符分配保存编码的空间 */trcpy(HC[k], &cd[sp]);}free(cd);
}

课本P154例子非常重要。