数据结构数和二叉树.pptVIP

* A B C D E F G H J I A B C D E F G H J I A B C D E F G H J I 森林转二叉树举例：（法二） 兄弟相连 长兄为父 孩子靠左 头根为根 A * 讨论4：二叉树如何还原为森林？ 要点：把最右边的子树变为森林，其余右子树变为兄弟 A B C D E F G H J I A B C D E F G H J I E F A B C D G H J I 即B={root, LB, RB} F={T1, T2, …,Tm} * 树的遍历可有三条有哪些信誉好的足球投注网站路径： 先根序（次序）遍历 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 后根（次序）遍历 若树不空，则先依次后根遍历各棵子树，然后访问根结点。 按层次遍历 若树不空，则自上而下自左至右访问树中每个结点。 * C F E B A D G H I J K 先根遍历时顶点的访问次序： A B E F C D G H I J K 后根遍历时顶点的访问次序： E F B C I J K H G D A 层序遍历时顶点的访问次序： A B C D E F G H I J K * 先序遍历 若森林为空，返回； 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历 若森林为空，返回； 中序遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 中序遍历除去第一棵树之后剩余的树构成的森林。 森林的遍历 A B C D E F G H J I * A B C D E F G H K I A B C D E F G L J * 路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： 霍 夫 曼 树： 6.5 Huffman树及其应用 一、最优二叉树（霍夫曼树） 由一结点到另一结点间的分支所构成 路径上的分支数目 从树根到每一结点的路径长度之和。 结点到根的路径长度与结点上权的乘积 预备知识：若干术语 d e b a c f g 树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。 a→e的路径长度＝ 树长度＝ 2 10 * Huffman树简介： 树的带权路径长度如何计算？ WPL = ?wklk k=1 n a b d c 7 5 2 4 (a) c d a b 2 4 5 7 (b) b d a c 7 5 2 4 (c) 经典之例： WPL=36 WPL=46 WPL= 35 哈夫曼树则是：WPL 最小的树。 Huffman树 Weighted Path Length * (1) 由给定的 n 个权值{w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二叉树的森林F = { T0, T1, T2, …, Tn-1 }，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： ① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在 F 中删去这两棵二叉树。 ③ 把新的二叉树加入 F。 构造霍夫曼树的基本思想： 构造Huffman树的步骤（即Huffman算法）： 权值大的结点用短路径，权值小的结点用长路径。 先举例！ * 操作要点：对权值的合并、删除与替换 ——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权 构造Huffman树的步骤： 注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。 6.2.2 赫夫曼编码 * 例2：设有4个字符d,i,a,n，出现的频度分别为7,5,2, 4，怎样编码才能使它们组成的报文在网络中传得最快？ 法1：等长编码。例如用二进制编码来实现。 取 d=00，i=01，a=10，n=11 法2：不等长编码，例如用前缀编码来实现。 取 d=0; i=10, a=110, n=111 a d i n 0 0 0 1 1 1 用 二 叉 树 来 设 计 前 缀 编 码 最快的编码是哪个？ 是非等长的前缀编码！ 任一个字符的编码都不是另一个字符编码的前缀 约定： 左分支表示0 右分支表示1 则从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子的编码。 * A C B D E K F G H I J * 如何得到电文长度最短的二进制前缀编码？ 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 d,i,a,n，出现的频度分别为7,5,2,4 假设每种字符在电文中出现的次