第五六章树与二叉树9.ppt

三、哈夫曼树的应用(哈夫曼编码) 首先，译码要唯一，即对字符进行编码后，能够唯一翻译成原来的字符。 其次，各个字符的编码要尽可能短，只有这样才能使编码后最短。 注意：达到其一，很容易！ 例如，达到译码唯一 假设有8个字符，我们用长度是3的二进制编码即可： 000 001 010 011 100 101 110 111 我 的 给 你 好 不 她 他 0 1 10 11 100 101 110 111 我 的 给 你 好 不 她 他 例如，尽可能短 那能译成什么？ 如何给数据文件中的字符编以不定长的编码，并且不用分隔符也不产生二义性，还要使各种数据文件平均长度最短？ 一、如何设计不定长码 如果在一个编码系统中，任一个字符的编码都不是另一个字符的编码的前缀（最左子串）。这种编码称作前缀编码。 例如： 01 001 010 100 110 我 给 你 的 好 那能译成什么？ 构造方法： 用被编码的字符作为叶子，构造二叉树，然后在二叉树的左分支上标“０”,右分支标”1”，每个字符的编码就是从根到该字符叶子所经路径上的０、１序列。 你 我 给 的 好 我=00 给=01 你=100 的=101 好=11 0 0 0 0 1 1 1 1 二、平均长度最短 哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。 设要传送的字符为： ABACCDA 若编码为 ：A—0 B—110 C—10 D---111 0110010101110 A C B D 0 0 0 1 1 1 规定： 左分支用“0”表示； 右分支用“1”表示 要使传输过程中的编码尽量短，应使频率高的字编码短。——哈夫曼树 例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。 0 0 1 1 1 0 1 14 8 4 6 4 2 2 3 3 T B A C S 步骤1：确定W（权）={2，4，2，3，3} 步骤2：构造哈夫曼树 步骤3：给出哈夫曼编码 T B A C S 00 01 10 110 111 0 巩固练习 有一组数值24、21、12、15、28，画出对应的哈（赫）夫曼树，并计算其WPL 在一份电文中共使用8种字符，即a, b, c, d, e, f, g, h，它们出现的频率依次为0.10, 0.09, 0.32, 0.02,0.26, 0.03, 0.01, 0.17 ，试画出对应的赫夫曼树，求出每个字符的赫夫曼编码。 假定用于通信的电文仅由a,b,c,d 4个数据元素，各字母在电文中出现的频率分别为7，5，9，4，试为这4个字母设计不等长的哈夫曼编码。（要求画出哈夫曼树，给出编码，并求出带权路径长度） 　1. 熟练掌握二叉树的结构特性 　4. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。 小 结 　1. 熟练掌握二叉树的结构特性 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　1. 熟练掌握二叉树的结构特性 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　3. 掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。 　4. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。 　5. 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。 * 处理的数据是棋盘的格局，结构是一对多，树形。 * * * 注意：二叉树是有序树。 * 第比数列前n项和：Sn=a1(1-q^n)/(1-q) =(a1-an*q)/(1-q) (q≠1) * 由于完全二叉树的性质，可知，度为一的结点数只能为一或为０． 当总结点数为偶数时，n1=1;总结点数为奇数时，n1=0. * １＼例4.1,用性质5来求解,就大编号为:700，其父结点为:350，从351开始，全都是叶子结点．所以：叶子结点的个数为：７００－３５０＝３５０ ２＼例4.1,用性质5来求解,就大编号为:２５７，其父结点为:１２８，从１２９开始，全都是叶子结点．所以：叶子结点的个数为：２５７－１２８＝１２９ * １、２^5=32，所以由性质４可知：log2^32+1=5+1 2、画出树。 ３、性质３ ４、多种解法。 *