树（四）2012初赛知识点梳理二叉树的应用二叉排序树哈夫曼树u 定义 二叉排序树是指具有以下性质的二叉树： 其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值；左右子树又是一棵二叉排序树。u 特点只要按中序遍历即可得到由小到大的有序序列。10318213211549892，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)：定义为树中所有叶结点 的带权路径长度之和，2347哈夫曼（Huffman）树又称最优二叉树。它是n个带权叶子结点构 成的所有二叉树中，带权路径长度WPL最小的二叉树构造哈夫曼树的过程（哈夫曼算法）根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二 叉树，令初始权值为wj；在森林中选取两棵根结点权值最小的树作左右子树，构造一棵 新的二叉树，置新二叉树根结点权值为其左右子树根结点权 值之和；在森林中删除这两棵树，同时将新得到的二叉树加入森林中；重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。哈夫曼树的形态不是唯一的，但对具有一组权值 的各哈夫曼树的WPL是唯一的。w=5,29,7,8,14,23,3,11，构造哈夫曼树85311192342291487152958100WPL= (23+29) *2 + (11+14) *3+(3+5+7+8)*4=271w=5,29,7,8,14,23,3,11w=29,7,8,14,23,11,8w=29,14,23,11,8,15w=29,14,23,15,19w=29,23,19,29w=29,29,42w=42,58w=100在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的 二叉树，置新二叉树根结点权值为其左右子树根结点权值之和； 在森林中删除这两棵树，同时将新得到的二叉树加入森林中； 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。哈夫曼树的形态不是唯一的，但对具有一组权值 的各哈夫曼树的WPL是唯一的。4 7 12 8 9 23哈夫曼编码n背景n目前，远距离通信的主要手段是电报，即将需传送的文字转换成由二进 制的字符组成的字符串。n编码时需要遵循以下原则n解码的结果唯一；n发送的二进制编码尽可能短。n两类二进制编码n等长编码：各个字符的编码长度相等。n优点：解码简单。n缺点：编码长度可能不最短。n不等长编码：各个字符的编码长度不等。n优点：编码长度尽可能地短。n缺点：解码困难。等长编码什么情况下 空间效率高？不等长编码什么情况 下空间效率高？例如：传送电文“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序列，这样得到的编码称 为哈夫码编码。哈夫曼编码为前缀编码。以这组编码传送电文可使电文总长最短(对所有其它前缀编码而言)。vuiywtre字符集vwertyui频率5297814233110000000111111100100000111011111110100001iuytrewv哈夫曼解码从哈夫曼树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦 到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。vuiywtre00000001111111解码：111111100001001111010结果：reviewtg915最优前缀编码，也称Huffman编码。这种编码组合的特点是 对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率 。下面编码组合哪一组不是合法的前缀编码。 A)（00，01，10，11） B)（0，1，00，11） C)（0，10，110，111） D)（1，01，000，001） 0是00的前缀码，这部分是数据结构中哈夫曼编码处的知识。 编码和解码 数据压缩过程称为编码。即将文件中的每个字符均转换为一个 惟一的二进制位串。 数据解压过程称为解码。即将二进制位串转换为对应的字符。 前缀码：给定一个序列的集合，若不存在一个序列是另一个序列 的前缀，则该序列集合称为前缀码。最优2叉树产生的前缀码称为 最佳前缀码，