第六章 树和二叉树详解.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 01 10 110 111 9 5 6 2 7 7 13 16 29 例子 例 某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05,0.29,0.07,0.08, 0.14,0.23, 0.03,0.11。构造以字符使用频率作为权值的哈夫曼树。将权值取为整数w=(5,29,7,8,14,23,3,11)，按哈夫曼算法构造的一棵哈夫曼树如下： 对应字符的编码 a: 0110 b: 10 c: 1110 d: 1111 e: 110 f: 00 g: 0111 h: 010 1）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉树； 2）将该二叉树所有右分枝标记1，所有左分枝标记0； 3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码； 29 19 58 42 100 15 8 7 3 5 8 11 23 14 29 a b e c d f h g Huffman树算法及时间复杂度分析 输入： n个字符的集合C={c1,…cn}及其频度={f1,…fn} 输出：C的Huffman树 1.根据频度，将所有字符建立最小堆 H //?(n) 2. V←C; T={} 3. for j←1 to n-1 //n个节点经n-1次合并，每次少1个节点 4. c←Delete_Min(H) // ?log(n-1)? + ?log(n-2)? +…+?log2?+?log1? =?(nlogn) 5. c’←Delete_Min(H) // ?log(n-2)? + ?log(n-3)?+…+ ?log1? =?(nlogn) 6. f(v) ←f(c)+ f(c’) 7. INSERT(H,v) // ?log(n-1)? + ?log(n-2)? +…+ ?log2? =?(nlogn) 8. V=V∪{v} // ?(1)*(n-1)= ?(n) 9. T=T∪{(v,c), (v, c′)} 10. end while //总时间复杂度?(nlogn) 　1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 　2. 熟悉二叉树的各种存储结构的特点及适用范围。 　3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。 本章小结 　　4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。 　　5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 　　6. 学会编写实现树的各种操作的算法。 　　7. 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。 6.6 假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}, 为这8个字母设计哈夫曼编码。 上机题目：根据输入字符串创建树或二叉树，输出树或二叉树的先根遍历和后根遍历序列。 6.5 下述编码哪一组不是前缀码? {00,01,10,11}, {0,1,00,11}, {0,10,110,111} 作业 * * j和j+1层之间 * * * * * * * * * * * * * * * * * * * * * * * 由此，树的各种操作均可对应二叉树的操作来完成。 应当注意的是，和树对应的二叉树，其左、右子树的概念 已改变为： 左是孩子，右是兄弟。 6.4.3 树和森林的遍历 一、树的遍历 二、森林的遍历 三、树的遍历的应用 树的遍历可有三条搜索路径: 按层次遍历: 先根(次序)遍历: 后根(次序)遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 若树不空，则先依次后根遍历各棵子