[理学]霍夫曼树的详细讲解.ppt

Data Structure Chpter 6: Binary Tree Chpter 6: Binary Tree Data Structure College of Science, Xidian University 第六章 树与二叉树(III) 西安电子科技大学·理学院 hjTang@xidian.edu.cn 树的遍历 先根遍历 先访问树的根结点 先根遍历树的第i棵子树 RADEBCFGHK(对应二叉树的先序序列) 后根遍历 后根遍历树的第i棵子树 再访问树的根结点 DEABGHKFCR（对应二叉树的中序序列） 森林的遍历 先序遍历森林 访问森林中的第一棵树的根结点 先序遍历第一棵树中根结点的子森林 先序遍历除去第一棵树后剩余的森林 ADEBCFGHK（对应二叉树的先序序列） 中序遍历森林 中序遍历森林中的第一棵树根结点的子树森林 访问第一棵树的根节点 中序遍历除去第一棵树后剩余的森林 DEABGHKFC（对应二叉树的中序序列） 主要内容 最优二叉树(Haffman树) 最优二叉树的定义 最优二叉树的求法 Haffman编码 回溯法与树的遍历 幂集 八皇后问题 最优二叉树(Huffman树) 基本概念 路径长度——一个结点到另一个结点的分支 树的路径长度——树根到每一个结点的路径长度之和 左图：树的路径长度＝1+1+2+2+2+2=10 右图：树的路径长度＝1+1+2+2+3+3=12 路径长度最短的二叉树——完全二叉树 带权路径 树的带权路径长度——所有叶结点的带权路径长度 WPL1=7×2＋5×2＋2×2＋4×2＝36 WPL2=4×2＋7×3＋5×3＋2×2＝46 WPL3=7×2＋5×2＋2×3＋4×3＝35 Huffman树的定义 最优二叉树——n个权值为{w1…wk}，构造一棵二叉树，每个叶结点的权为wi, 则具有最小WPL值的二叉树称之为最优二叉树（Huffman树） Huffman树的应用举例 编制一个程序，将100分制换算成5分制(假定人数为10000人) 最优比较树 问题？ 是否最优比较树(二叉树)一定是 的？ ——错！大部分情况都不是 Huffman树的构造(Huffman算法) 根据给定的n 个权值{w1, …, wn}构造n棵二叉树的集合F={T1, …, Tn}, 其中每棵二叉树Ti中只有一个带权为wi的根节点,左右子树为空 在F中找出两棵根节点的权最小的树作为左右子树构造一棵新的二叉树，且新的二叉树根结点的权值为左右子树上根结点的权值之和 在F中删除这两棵树，同时将新得到的树加入F中 重复2、3步，直至F中只剩下一棵树为止 Huffman算法举例1 Huffman树构造算法举例2 Huffman树与压缩编码 在一篇文章中出现了8种字符(A…H), 每种字符出现的概率如下表所示，试给出一种编码，使得所用比特数最少。 使用Huffman编码 Huffman编码与解码 Huffman编码 对数据进行压缩存储步骤 对数据进行统计，统计每种符号发生的概率 根据符号概率的大小，生成Huffman树 根据Huffman树对每个符号编写(编)码表 按照给定的码表对数据进行编码 解码时需要原编码方案 例题 将下面的句子采用尽可能少的编码进行存储 Can you imagine an imaginary menagerie manager imagining managing an imaginary menagerie? 你可以想象一个虚构的野生动物园经理幻想自己管理一个虚构的野生动物园吗？ 分析 出现字符及其频度（11种字符，共77字符）： 采用普通编码 11字符，231124: 通用码表：见右图 字符串编码（308 bits）： 采用Huffman编码 根据频度生成Huffman树 进行编码 采用Huffman编码 can you imagine an imaginary menagerie manager imagining managing an imaginary menagerie 编码结果(238 bits)： 回溯法与树的遍历 在求解的过程中不断的使用“尝试”的方法判断当前状态是否可行，可行则继续“尝试” 回溯，也称回滚，典型的递归 对应于二叉树的先序遍历算法 遍历的二叉树并非预先已建立，而是隐藏在遍历的过程中 回溯法与树的遍历 例1 求含有n个元素的集合的幂集 （1, 2, 3)的幂集有8个 幂集算法 例2 八皇后问题 在8×8的国际棋盘上放置八个皇后，要求这八个皇后相互不能攻击(同行，同列，斜线) 例2 八皇后问题 例2 八皇后问题 void Trial(int i, int n) if (i = n) 输出当前布局 else for (j=0;