镇江网站建设制作,大同市建设工程质量监督站网站,搜索引擎排名原理,北京海淀区邮编文章目录 6.5 树与森林6.5.1 树的存储结构1. 双亲表示法(顺序存储结构)2 孩子链表表示法3 孩子兄弟表示法(二叉树表示法) 6.5.2 森林与二叉树的转换1 树转换成二叉树2 二叉树转换成树3 森林转换成二叉树4 二叉树转换成森林 6.5.3 树和森林的遍历1. 树的遍历2. 森林的遍历 6.6 赫… 文章目录 6.5 树与森林6.5.1 树的存储结构1. 双亲表示法(顺序存储结构)2 孩子链表表示法3 孩子兄弟表示法(二叉树表示法) 6.5.2 森林与二叉树的转换1 树转换成二叉树2 二叉树转换成树3 森林转换成二叉树4 二叉树转换成森林 6.5.3 树和森林的遍历1. 树的遍历2. 森林的遍历 6.6 赫夫曼树及其应用6.6.1 最优二叉树(Huffman树)1 基本概念2 Huffman树的构造 6.6.2 赫夫曼编码及其算法1. Huffman编码2. Huffman编码算法实现 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 n n 个结点度为 k k k 的树中必有 n ( k − 1 ) 1 n(k-1)1 n(k−1)1 空指针域。
(2) 不定长结点结构
树中每个结点的指针域数量不同是该结点的度如图6-14(b) 所示。没有多余的指针域但操作不便。
(3) 复合链表结构 n n n 个结点的树有 n n n 个单链表(叶子结点的孩子链表为空)而 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 是其父结点的左子树的根结点则将该结点 i i i 的右子结点以及沿右子链不断地搜索所有的右子结点将所有这些右子结点与 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 ( root LB RB ) B(\operatorname{root}\operatorname{LB}\operatorname{RB}) B(rootLBRB)
① 若 $F\varnothing $则 B B B 为空树 ② 若 F F F 非空即 n ≠ 0 n\ne 0 n0则 B B B 的根 r o o t root root 即为森林中第一棵树的根 r o o t ( T 1 ) root(T_1) root(T1)而其右子树 R B RB RB 是从森林 F ’ { T 2 , T 3 , ⋯ , T n } F’\{T_2, T_3,⋯,T_n\} F’{T2,T3,⋯,Tn} 转换而成的二叉树。
4 二叉树转换成森林
若 B ( r o o t L B R B ) B(rootLBRB) B(rootLBRB) 是一棵二叉树则可以将其转换成由若干棵树构成的森林 F { T 1 , T 2 , ⋯ , T n } F\{T_1, T_2,⋯,T_n\} F{T1,T2,⋯,Tn} 。
转换算法
① 若 B B B 是空树则 F F F 为空。 ② 若 B B B 非空则 F F F 中第一棵树 T 1 T_1 T1 的根 r o o t ( T 1 ) root(T_1) root(T1) 就是二叉树的根 r o o t root root T 1 T_1 T1 中根结点的子森林 F 1 F1 F1 是由树 B B B 的左子树 L B LB LB 转换而成的森林 F F F 中除 T 1 T_1 T1 外其余树组成的的森林 F ’ { T 2 , T 3 , ⋯ , T n } F’\{T_2, T_3,⋯,T_n\} F’{T2,T3,⋯,Tn} 是由 B B B 右子树 R B RB RB 转换得到的森林。
上述转换规则是递归的可以写出其递归算法。以下给出具体的还原步骤。
6.5.3 树和森林的遍历
1. 树的遍历
由树结构的定义可知树的遍历有二种方法。
先序遍历先访问根结点然后依次先序遍历完每棵子树。如图6-23的树先序遍历的次序是 A B C D E F G I J H K ABCDEFGIJHK ABCDEFGIJHK后序遍历先依次后序遍历完每棵子树然后访问根结点。如图6-23的树后序遍历的次序是 C D B F I J G H E K A CDBFIJGHEKA CDBFIJGHEKA 说明 ◆ 树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。 ◆ 树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同。 对于一般的树而言并没有明显的左右子树之分因此在树上定义中序遍历并不合理。对于一般的树我们主要考虑先遍历根节点还是遍历子树。 其实树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历逻辑上是很好理解的根节点是没有右子树的。那么二叉树实际上逻辑理解就是先访问根结点然后访问他的其余子树。对于有右节点的子树的根根左右可以理解成先访问根然后访问根下的那棵树最后再去访问子树森林中的其他树。这样的逻辑结果就和树的遍历中的先序遍历完全一致了。 2. 森林的遍历
设 F { T 1 , T 2 , ⋯ , T n } F\{T_1, T_2,⋯,T_n\} F{T1,T2,⋯,Tn} 是森林对 F F F 的遍历有二种方法。 ⑴ 先序遍历按先序遍历树的方式依次遍历 F F F 中的每棵树。 ⑵ 中序遍历按中序遍历树的方式依次遍历 F F F 中的每棵树。
6.6 赫夫曼树及其应用
赫夫曼(Huffman)树又称最优树是一类带权路径长度最短的树有着广泛的应用。
6.6.1 最优二叉树(Huffman树)
1 基本概念
① 结点路径从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。
② 路径长度结点路径上的分支数目称为路径长度。
③ 树的路径长度从树根到每一个结点的路径长度之和。
例图6-23的树。 A A A 到 F F F 结点路径 A E F AEF AEF 路径长度(即边的数目) 2 2 2 树的路径长度 3 × 1 5 × 2 2 × 3 19 3\times 15\times22\times319 3×15×22×319 ④ 结点的带权路径长度从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积。
⑤ 树的带权路径长度树中所有叶子结点的带权路径长度之和记做 W P L w 1 × l 1 w 2 × l 2 ⋯ w n × l n ∑ w i × l i ( i 1 , 2 , ⋯ , n ) W P Lw_{1} \times l_{1}w_{2} \times l_{2}\cdotsw_{n} \times l_{n}\sum w_{i} \times l_{i} \quad(i1,2, \cdots, n) WPLw1×l1w2×l2⋯wn×ln∑wi×li(i1,2,⋯,n)
其中 n n n 为叶子结点的个数 w i w_i wi为第 i i i 个结点的权值 l i l_i li 为第 i i i 个结点的路径长度。
⑥ Huffman树具有 n n n 个叶子结点(每个结点的权值为 w i w_i wi) 的二叉树不止一棵但在所有的这些二叉树中必定存在一棵 W P L WPL WPL 值最小的树称这棵树为 Huffman 树(或称最优树) 。
在许多判定问题时利用 Huffman 树可以得到最佳判断算法。如图6-24是权值分别为 2 、 3 、 6 、 7 2、3、6、7 2、3、6、7具有 4 4 4 个叶子结点的二叉树它们的带权路径长度分别为 ( a ) W P L 2 × 2 3 × 2 6 × 2 7 × 2 36 ( b ) W P L 2 × 1 3 × 2 6 × 3 7 × 3 47 ( c ) W P L 7 × 1 6 × 2 2 × 3 3 × 3 34 \begin{aligned} (a) WPL 2 \times 23 \times 26 \times 27 \times 236 \\ (b) WPL2 \times 13 \times 26 \times 37 \times 347 \\ (c) W P L7 \times 16 \times 22 \times 33 \times 334 \\ \end{aligned} (a)WPL2×23×26×27×236(b)WPL2×13×26×37×347(c)WPL7×16×22×33×334
其中(c)的 W P L WPL WPL 值最小可以证明是 Huffman 树。 2 Huffman树的构造
① 根据 n n n 个权值 { w 1 , w 2 , ⋯ , w n } \{w_1, w_2, ⋯,w_n\} {w1,w2,⋯,wn}构造成 n n n 棵二叉树的集合 F { T 1 , T 2 , ⋯ , T n } F\{T_1, T_2, ⋯,T_n\} F{T1,T2,⋯,Tn}其中每棵二叉树只有一个权值为 w i w_i wi 的根结点没有左、右子树
② 在 F F F 中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树且新的二叉树根结点权值为其左、右子树根结点的权值之和
③ 在 F 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 是 W P L 6 × 2 3 × 3 4 × 3 8 × 2 5 × 3 5 × 3 79 \mathrm{WPL}6 \times 23\times 34\times 38\times 25\times 35\times 3 79 WPL6×23×34×38×25×35×379
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 a,b, c,d, e,f a,b,c,d,e,f 所对应的 Huffman 编码分别是 10 010 011 00 110 111 1001001100 110111 1001001100110111。 2. Huffman编码算法实现
(1) 数据结构设计
Huffman 树中没有度为 1 的结点。若有 n n n 个叶子结点的 Huffman 树共有 2 n − 1 2n-1 2n−1 个结点则可存储在大小为 2 n − 1 2n-1 2n−1 的一维数组中。实现编码的结点结构如图6-26所示。 #define MAX_NODE 200 /* Max_Node2n-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;m2*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 树后树的根结点的下标是 2 n − 1 2n-1 2n−1即 m − 1 m-1 m−1 。
(3) Huffman编码算法
根据出现频度(权值) Weight对叶子结点的Huffman 编码有两种方式 ① 从叶子结点到根逆向处理求得每个叶子结点对应字符的 Huffman 编码。 ② 从根结点开始遍历整棵二叉树求得每个叶子结点对应字符的 Huffman 编码。
算法实现
void Huff_coding(unsigned n, Hnode HT[]Huffmancode HC)
/* m应为n1,编码的最大长度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例子非常重要。
