2011-2012初赛知识点讲解数据结构（九）树.ppt

构造哈夫曼树的过程（哈夫曼算法） 根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令初始权值为wj； 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和； 在森林中删除这两棵树，同时将新得到的二叉树加入森林中； 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。 w={5,29,7,8,14,23,3,11}，构造哈夫曼树 哈夫曼编码 背景 目前，远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。 编码时需要遵循以下原则 解码的结果唯一； 发送的二进制编码尽可能短。 两类二进制编码 等长编码：各个字符的编码长度相等。 优点：解码简单。 缺点：编码长度可能不最短。 不等长编码：各个字符的编码长度不等。 优点：编码长度尽可能地短。 缺点：解码困难。 例如：传送电文“ABACCDA” 等长编码 A：00 B：01 C：10 D：11 编码结果00010010101100，长度为14位。 解码方以两位为一字段解码。 不等长编码 原则：出现次数较多的字符编码短，次数较少的字符编码长。 A：0 B：00 C：1 D：01 编码结果000011010，长度为9位。 解码方无法解码，因为解码的结果不唯一。 前缀编码 任意一个字符的编码都不能是另一个字符的编码的前缀，这种编码称为前缀编码。 哈夫曼编码（同时满足代码长度短，且解码唯一） 目标：使电文总长最短。 以字符出现的次数为权，构造一棵赫夫曼树；将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列，这样得到的编码称为哈夫码编码。 哈夫曼编码为前缀编码。 以这组编码传送电文可使电文总长最短(对所有其它前缀编码而言)。 哈夫曼解码 从哈夫曼树根开始，从待译码电文中逐位取码。 若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符； 再重新从根出发，直到电文结束。 树（四） 2012初赛知识点梳理 二叉树的应用 二叉排序树 哈夫曼树 定义 二叉排序树是指具有以下性质的二叉树： 其左子树上所有结点的数据值均小于根结点的数据值； 右子树上所有结点的数据值均大于或等于根结点的数据值； 左右子树又是一棵二叉排序树。 特点 只要按中序遍历即可得到由小到大的有序序列。 10 3 18 2 13 21 15 4 9 8 9 {2，3，4，8，9，9，10，13，15，18，21} 中序遍历 二叉排序树(Binary Sort Tree)又称二叉查找(有哪些信誉好的足球投注网站)树(Binary Search Tree)。 二叉排序树的建立 对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同。 【例6.7】下图(a)所示的树，是按如下插入次序构成的： ??????? 45，24，55，12，37，53，60，28，40，70 ???? 下图(b)所示的树，是按如下插入次序构成的： 12，24，28，37，40，45，53，55，60，70 ①二叉排序树查找成功的平均查找长度 ??? 　在等概率假设下，下面(a)图中二叉排序树查找成功的平均查找长度为 在等概率假设下，(b)图所示的树在查找成功时的平均查找长度为： ?????????? ASLb=(1+2+3+4+5+6+7+8+9+10)/10=5.5 与二分查找类似，和关键字比较的次数不超过树的深度。 ②在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关 哈夫曼树 路径：从树中一个结点到另一个结点之间的分支。 路径长度：路径上的分支数目称为路径长度。 树的路径长度：从树根到每一结点的路径长度之和。 结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。 树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和， 2 3 4 7 哈夫曼（Huffman）树又称最优二叉树。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树 哈夫曼树的形态不是唯一的，但对具有一组权值的各哈夫曼树的WPL是唯一的。 8 5 3 11 19 23 42 29 14 8 7 15 29 58 100 WPL= (23+29) *2 + (11+14) *3+(3+5+7+8)*4=271 w={5,29,7,8,14,23,3,11} w={29,7,8,14,23,11,8} w={29,14,23,11,8,15} w={29,14,23,15,19} w={