数据结构树与二叉树.ppt

1 第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序 目录 2 第6章树和二叉树 Tree BinaryTree 6 1树的基本概念6 2二叉树6 3遍历二叉树和线索二叉树6 4树和森林6 5赫夫曼树及其应用 特点 非线性结构 一个直接前驱 但可能有多个直接后继 一对多 或称1 n 3 6 1树的基本概念 6 1 1树的定义6 1 2若干术语6 1 3逻辑结构6 1 4存储结构6 1 5树的运算 4 6 1 1树的定义 注1 过去许多书籍中都定义树为n 1 曾经有 空树不是树 的说法 但现在树的定义已修改 注2 树的定义具有递归性 即 树中还有树 由一个或多个 n 0 结点组成的有限集合T 有且仅有一个结点称为根 root 当n 1时 其余的结点分为m m 0 个互不相交的有限集合T1 T2 Tm 每个集合本身又是棵树 被称作这个根的子树 5 6 1 2若干术语 即上层的那个结点 直接前驱 即下层结点的子树的根 直接后继 同一双亲下的同层结点 孩子之间互称兄弟 即双亲位于同一层的结点 但并非同一双亲 即从根到该结点所经分支的所有结点 即该结点下层子树中的任一结点 根叶子森林有序树无序树 即根结点 没有前驱 即终端结点 没有后继 指m棵不相交的树的集合 例如删除A后的子树个数 双亲孩子兄弟堂兄弟祖先子孙 结点各子树从左至右有序 不能互换 左为第一 结点各子树可互换位置 6 即树的数据元素 结点挂接的子树数 结点结点的度结点的层次终端结点分支结点 树的度树的深度 或高度 从根到该结点的层数 根结点算第一层 即度为0的结点 即叶子 即度不为0的结点 也称为内部结点 所有结点度中的最大值 Max 各结点的度 指所有结点中最大的层数 Max 各结点的层次 问 右上图中的结点数 树的度 树的深度 13 3 4 有几个直接后继就是几度 亦称 次数 7 树的抽象数据类型定义 见教材P118 119 ADTTree 数据对象D 数据关系R 基本操作P ADTTree D是具有相同特性的数据元素的集合 若D为空集 则称为空树 允许n 0若D中仅含一个数据元素 则R为空集 其他情况下的R存在二元关系 root唯一 关于根的说明 Dj Dk 关于子树不相交的说明 关于数据元素的说明 至少有15个 如求树深 求某结点的双亲 8 6 1 3树的逻辑结构 一对多 1 n 有多个直接后继 如家谱树 目录树等等 但只有一个根结点 且子树之间互不相交 6 1 4树的存储结构 讨论1 树是非线性结构 该怎样存储 特点 仍然有顺序存储 链式存储等方式 9 讨论3 树的链式存储方案应该怎样制定 复原困难 可用多重链表 一个前趋指针 n个后继指针 细节问题 树中结点的结构类型样式该如何设计 即应该设计成 等长 还是 不等长 缺点 等长结构太浪费 每个结点的度不一定相同 不等长结构太复杂 要定义好多种结构类型 可否规定为 从上至下 从左至右将树的结点依次存入内存 有重大缺陷 不能唯一复原就没有实用价值 讨论2 树的顺序存储方案应该怎样制定 困惑 到底应当开多少个链域 补充 树的5种表示法 图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子 右兄弟表示法 意义 把一般的树转化为最简单 最有规律的二叉树再研究 然后设法从二叉树再转回多叉树 11 图形表示法 湖北理工学院 叶子 根 子树 12 嵌套集合表示法 13 A B E K L F C G D H M I J 约定 根作为由子树森林组成的表的名字写在表的左边 广义表表示法 14 凹入表示法 又称目录表示法 15 左孩子 右兄弟表示法 意义 多叉树转为二叉树 16 方法 加线 抹线 旋转 树转二叉树举例 兄弟相连 长兄为父 孩子靠左 特点是 根结点没有右孩子 17 讨论 二叉树怎样还原为树 要点 逆操作 把所有右孩子变为兄弟 18 6 1 5树的运算 要明确 1 普通树 即多叉树 若不转化为二叉树 则运算很难实现 2 二叉树的运算仍然是插入 删除 修改 查找 排序等 但这些操作必须建立在对树结点能够 遍历 的基础上 本章重点 二叉树的表示和实现 遍历 指每个结点都被访问且仅访问一次 不遗漏不重复 19 6 2二叉树 为何要重点研究每结点最多只有两个 叉 的树 二叉树的结构最简单 规律性最强 可以证明 所有树都能转为唯一对应的二叉树 不失一般性 6 2 1二叉树的定义6 2 2二叉树的性质6 2 3二叉树的存储结构 注 二叉树最重要的运算是 遍历 20 6 2 1二叉树的定义 定义 是n n 0 个结点的有限集合 由一个根结点以及两棵互不相交的 分别称为左子树和右子树的二叉树组成 逻辑结构 一对二 1 2 基本特征 每个结点最多只有两棵子树 不存在度大于2的结点 左子树和右子树次序不能颠倒 问 具有3个结点的二叉树可能有几种不同形态 有5种 基本形态 一般的树有几种 21 二叉树的抽象数据类型定义 见教材P121 122 ADTBinaryTree 数据对象D 数据关系R 基本操作P ADTBinaryTree D是具有相同特性的数据元素的集合 若D 则R 若D 则R H 存在二元关系 root唯一 关于根的说明 Dj Dk 关于子树不相交的说明 关于数据元素的说明 关于左子树和右子树的说明 至少有20个 如返回某结点的左孩子 或中序遍历 等等 22 6 2 2二叉树的性质 3 2 讨论1 第i层的结点数最多是多少 利用二进制性质可轻松求出 性质1 在二叉树的第i层上至多有2i 1个结点 i 0 性质2 深度为k的二叉树至多有2k 1个结点 k 0 再提问 第i层上至少有个结点 1 讨论2 深度为k的二叉树 最多有多少个结点 利用二进制性质可轻松求出 2i 1个 2k 1个 23 3 深度为9的二叉树中至少有个结点 9 8 9 1 2 深度为 的二叉树的结点总数 最多为个 k 1 log2k k k 1 树 中各结点的度的最大值称为树 的 高度 层次 深度 度 D C C 课堂练习 24 性质3 对于任何一棵二叉树 若2度的结点数有n2个 则叶子数 n0 必定为n2 1 即n0 n2 1 证明 二叉树中全部结点数n n0 n1 n2 叶子数 1度结点数 2度结点数 又 二叉树中全部结点数n B 1 总分支数 根结点 除根结点外 每个结点必有一个直接前趋 即一个分支 而总分支数B n1 2n2 1度结点必有1个直接后继 2度结点必有2个 三式联立可得 n0 n1 n2 n1 2n2 1 即n0 n2 1 物理意义 叶子数 2度结点数 1 讨论 二叉树的叶子数和度为2的结点数之间有关系吗 25 完全二叉树 深度为k的 有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应 为何要研究这两种特殊形式 因为它们在顺序存储方式下可以复原 讨论 满二叉树 一棵深度为k且有2k 1个结点的二叉树 特点 每层都 充满 了结点 解释 完全二叉树的特点是只有最后一层叶子不满 且全部集中在左边 但这其实是顺序二叉树的含义 而图论中的 完全二叉树 是指n1 0的情况 满二叉树和完全二叉树有什么区别 答 满二叉树是叶子一个也不少的树 而完全二叉树虽然前k 1层是满的 但最底层却允许在右边缺少连续若干个结点 满二叉树是完全二叉树的一个特例 26 性质4 具有n个结点的完全二叉树的深度必为 log2n 1 性质5 对完全二叉树 若从上至下 从左至右编号 则编号为i的结点 其左孩子编号必为2i 其右孩子编号为2i 1 其双亲的编号必为i 2 i 1时为根 除外 证明 根据性质2 深度为k的二叉树最多只有2k 1个结点 且完全二叉树的定义是与同深度的满二叉树前面编号相同 即它的总结点数n位于k层和k 1层满二叉树容量之间 即2k 1 1 n 2k 1或2k 1 n 2k三边同时取对数 于是有 k 1 log2n k因为k是整数 所以k log2n 1 可根据归纳法证明 对于两种特殊形式的二叉树 满二叉树和完全二叉树 还特别具备以下2个性质 27 一棵完全二叉树有1000个结点 则它必有个叶子结点 有个度为2的结点 有个结点只有非空左子树 有个结点只有非空右子树 例 489 488 1 0 分析题意 已知n 1000 求n0和n2 还要判断末叶子是挂在左边还是右边 正确答案 全部叶子数 1000 2 500个 度为2的结点 叶子总数 1 499个 因为最后一个结点坐标是偶数 所以必为左子树 请注意 叶子结点总数 末层叶子数 28 6 2 3二叉树的存储结构 一 顺序存储结构按二叉树的结点 自上而下 从左至右 编号 用一组连续的存储单元存储 ABCDEFGHI 问 顺序存储后能否复原成唯一对应的二叉树形状 答 若是完全 满二叉树则可以做到唯一复原 而且有规律 下标值为i的双亲 其左孩子的下标值必为2i 其右孩子的下标值必为2i 1 即性质5 例如 对应 2 的两个孩子必为 4 和 5 即B的左孩子必是D 右孩子必为E T 0 一般不用 29 讨论 不是完全二叉树怎么办 答 一律转为完全二叉树 方法很简单 将各层空缺处统统补上 虚结点 其内容为空 AB C D E 缺点 浪费空间 插入 删除不便 30 二 链式存储结构用二叉链表即可方便表示 二叉树结点数据类型定义 typedefstructnode tree pointer typedefstructnode intdata tree pointerleft child right child node 一般从根结点开始存储 相应地 访问树中结点时也只能从根开始 注 如果需要倒查某结点的双亲 可以再增加一个双亲域 直接前趋 指针 将二叉链表变成三叉链表 31 二叉树链式存储举例 优点 不浪费空间 插入 删除方便 32 6 3遍历二叉树和线索二叉树 6 3 1遍历二叉树 遍历定义 遍历用途 遍历方法 指按某条搜索路线遍访每个结点且不重复 又称周游 它是树结构插入 删除 修改 查找和排序运算的前提 是二叉树一切运算的基础和核心 对每个结点的查看通常都是 先左后右 TraversingBinaryTree 33 遍历规则 二叉树由根 左子树 右子树构成 定义为D L R 以根结点为参照系 注 先 中 后 的意思是指访问的结点D是先于子树出现还是后于子树出现 D L R的组合定义了六种可能的遍历方案 LDR LRD DLR DRL RDL RLD若限定先左后右 则有三种实现方案 DLRLDRLRD先序遍历中序遍历后序遍历 34 例1 先序遍历的结果是 中序遍历的结果是 后序遍历的结果是 DBEACDEBCA 口诀 DLR 先序遍历 即先根再左再右LDR 中序遍历 即先左再根再右LRD 后序遍历 即先左再右再根 A B D E C DLR 先序遍历序列 ABDC 先序遍历 LDR 中序遍历序列 BDAC 中序遍历 LRD 后序遍历序列 DBCA 后序遍历 38 先序遍历结果 ABCDE 前缀表示法中序遍历结果A B C D E 中缀表示法后序遍历结果AB C D E 后缀表示法层次遍历结果 E D CAB 例2 用二叉树表示算术表达式 39 中序遍历算法LDR node root if root NULL LDR root lchild printf d root data LDR root rchild return 0 后序遍历算法LRD node root if root NULL LRD root lchild LRD root rchild printf d root data return 0 结点数据类型自定义typedefstructnode intdata structnode lchild rchild node node root 先序遍历算法DLR node root if root NULL 非空二叉树 printf d root data 访问DDLR root lchild 递归遍历左子树DLR root rchild 递归遍历右子树 return 0 40 对遍历的分析 1 从前面的三种遍历算法可以知道 如果将print语句抹去 从递归的角度看 这三种算法是完全相同的 或者说这三种遍历算法的访问路径是相同的 只是访问结点的时机不同 从虚线的出发点到终点的路径上 每个结点经过3次 第1次经过时访问 是先序遍历第2次经过时访问 是中序遍历第3次经过时访问 是后序遍历 2 二叉树遍历的时间效率和空间效率时间效率 O n 每个结点只访问一次空间效率 O n 栈占用的最大辅助空间 精确值 树深为k的递归遍历需要k 1个辅助单元 41 例 严题集6 42 编写递归算法 计算二叉树中叶子结点的数目 思路 叶子的特点 左右指针均空 可选用任何一种遍历算法查找叶子 将其统计并打印出来 DLR node root 采用先序遍历的递归算法 if root NULL 非空二叉树条件 等效于if root if root lchild 42 用空格字符表示 无孩子 或指针为空 如何把二叉树存入电脑内 怎样建树 见教材P131例 例 将下面的二叉树以二叉链表形式存入计算机内 考虑1 输入结点时怎样表示 无孩子 考虑2 以何种遍历方式来输入和建树 将二叉树按先序遍历次序输入 ABC DE G F n 以先序遍历最为合适 让每个结点都能及时被连接到位 字符串输完后应当再加一特殊的结束符号 如 因为 无法惟一表示结束 43 建树算法 StatusCreateBiTree BiTree CreateBiTree 输入序列 ABC DE G F 44 特别讨论 若已知先序 或后序 遍历结果和中序遍历结果 能否 恢复 出二叉树 例 已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA 请画出这棵二叉树 分析 由后序遍历特征 根结点必在后序序列尾部 即A 由中序遍历特征 根结点必在其中间 而且其左部必全部是左子树的子孙 即BDCE 其右部必全部是右子树的子孙 即FHG 继而 根据后序中的DECB子树可确定B为A的左孩子 根据HGF子串可确定F为A的右孩子 以此类推 严题集6 31 请证明 由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树 45 已知中序遍历 BDCEAFHG已知后序遍历 DECBHGFA BDCE FHG A DCE A B B A C C DCE 详细说明 6 3 2线索二叉树 所以 空指针数目 2n n 1 n 1个 证明 因为用二叉链表存储包含n个结点的二叉树 结点必有2n个链域 见二叉链表数据类型说明 又因为除根结点外 二叉树中每一个结点有且仅有一个双亲 意即每个结点地址占用了双亲的一个直接后继 n个结点地址共占用了n 1个双亲的指针域 也就是说 只会有n 1个结点的链域存放指针 ThreadedBinaryTree 讨论 用二叉链表法 l child r child 存储包含n个结点的二叉树 结点的指针区域中会有多少个空指针 有n 1个 结论 用二叉链表法存储包含n个结点的二叉树 结点的指针区域中会有n 1个空指针 可以用它来存放当前结点的直接前驱和后继等线索 以加快查找速度 这就是线索二叉树的意义和用途 疑问1 二叉树是1 2的非线性结构 如何定义其惟一的直接后继 答 要遍历之后才能得到 且不同遍历算法得到的后继也不同 先依遍历规则把每个结点对应的前驱或后继线索预存起来 这叫做 线索化 疑问2 获得这种 直接前驱 或 直接后继 有何意义 答 从任一结点出发都能快速找到其前驱和后继 且不必借助堆栈疑问3 如何经济的 预先 存放这类信息 答 左孩子 前驱复用 右孩子 后继复用 后者称之为线索 约定 当Tag域为0时 表示正常情况 当Tag域为1时 表示线索情况 前驱 后继 左 右 孩子 为识别复用的两种不同信息 特增加两个标志域 问 增加了前驱和后继等线索有什么好处 能方便找出当前结点的前驱和后继 不用堆栈 递归 也能遍历整个树 疑问4 计算机如何识别是孩子指针还是线索指针 1 有关线索二叉树的几个术语 线索链表 线索 线索二叉树 线索化 用含Tag的结点样式所构成的二叉链表指向结点前驱和后继的指针加上线索的二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程 线索化过程就是在遍历过程中修改空指针的过程 将空的lchild改为结点的直接前驱 将空的rchild改为结点的直接后继 非空指针呢 仍然指向孩子结点 称为 正常情况 A G E I D J H C F B 例 带了两个标志的某先序遍历结果如下表所示 请画出对应的二叉树 A Ltag 1表示前驱线索Rtag 1表示后继线索 悬空 NIL 悬空 NIL 解 对该二叉树中序遍历的结果为 H D I B E A F C G所以添加线索应当按如下路径进行 为避免悬空态 应增设一个头结点 例1 画出以下二叉树对应的中序线索二叉树 2 线索二叉树的生成 线索化 线索化过程就是在遍历过程中修改空指针的过程 注 此图中序遍历结果为 H D I B E A F C G 对应的中序线索二叉树存储结构如图所示 例2 2000年计算机系考研题 给定如图所示二叉树T 请画出与其对应的中序线索二叉树 解 因为中序遍历序列是 5540256028083354对应线索树应当按此规律连线 即在原二叉树中添加虚线 NIL和NULL的值都是0 区别何在 在Delphi中NIL用来标记空指针 Null用来表示空的Variant型变量或是ASCII码为0的字符 比如用于标记字符串结束 在C C 中定义的宏NULL不加区别的包括了以上两种含义 可见ObjectPascal的语法要比C C 严谨得多 线索二叉树的生成算法 递归算法见教材P134 135 目的 在遍历二叉树的过程中修改空指针 添加前驱或后继的线索 使之成为线索二叉树 为了记下遍历过程中访问结点的先后次序 需要设置两个指针 p指针 当前结点之指针 pre指针 当前结点的前趋结点指针 设计技巧 依某种顺序遍历二叉树 对每个结点p 判断其左指针是否为空 以及其前驱结点的右指针是否为空 每次只修改前驱结点的右指针 后继 和本结点的左指针 前驱 参见算法6 6 若p lchild NULL 则 p Ltag 1 p lchild pre p的前驱线索应存p结点的左边若pre rchild NULL 则 pre Rtag 1 pre rchild p pre的后继线索应存pre结点的右边 3 线索二叉树的遍历 无需堆栈 对于线索二叉树的遍历 只要找到序列中的第一个结点 然后依次访问结点的后继直到后继为空为止 因为建立线索时已遍历一次 相当于线性化了 难点 在线索化二叉树中 并不是每个结点都能直接找到其后继的 当标志为0时 则需要通过一定运算才能找到它的后继 以中序线索二叉树为例 当RTag 1时 直接后继指针就在其rchild域内 当RTag 0时 直接后继是当前结点右子树最左下方的结点 请注意中序遍历规则是LDR 先左再根再右 5 当RTag 0时 表示有右孩子 此时应当从该结点的右孩子开始 p p rchild 查找左下角的子孙结点 即重复2 附 中序线索二叉树遍历步骤 算法6 5 1 设置一个搜索指针p 2 先寻找中序遍历之首结点 即最左下角结点 方法是 当LTag 0时 表示有左孩子 p p lchild 直到LTag 1 无左孩子 已到最左下角 首先访问p data 3 接着进入该结点的右子树 检查RTag和p rchild 4 若该结点的RTag 1 表示有后继线索 则p p rchild 访问p data 并重复4 直到后继结点的RTag 0 有后继找后继 无后继找右子树的最左子孙 有后继找后继 算法流程 先找最左子孙 找到最左子孙 无后继找右子树的最左子孙 6 4树和森林 6 4 1树和森林与二叉树的转换6 4 2树和森林的存储方式6 4 3树和森林的遍历 58 方法 加线 抹线 旋转 兄弟相连 长兄为父 孩子靠左 6 4 1树和森林与二叉树的转换 回顾1 树如何转为二叉树 左孩子 右兄弟表示法 59 回顾2 二叉树怎样还原为树 要点 逆操作 把所有右孩子变为兄弟 60 法一 各森林先各自转为二叉树 依次连到前一个二叉树的右子树上 讨论1 森林如何转为二叉树 法二 森林直接变兄弟 再转为二叉树 参见教材P138图6 17 两种方法都有转换示意图 法一和法二得到的二叉树是完全相同的 惟一的 61 森林转二叉树举例 用法二 森林直接变兄弟 再转为二叉树 兄弟相连长兄为父头树为根孩子靠左 A 62 讨论2 二叉树如何还原为森林 要点 把最右边的子树变为森林 其余右子树变为兄弟 63 6 4 2树和森林的存储方式 树有三种常用存储方式 双亲表示法 孩子表示法 孩子 兄弟表示法 指向左孩子 指向右兄弟 问 树 二叉树的 连线 抹线 旋转 如何由计算机自动实现 答 用 左孩子右兄弟 表示法来存储即可 存储的过程就是树转换为二叉树的过程 64 例如 65 66 因课时有限 树和森林的遍历 请自学 6 4 3树和森林的遍历 树的遍历 例如 先根序列 后根序列 abcde bdcea 深度优先遍历 先根 后根 广度优先遍历 层次 先根遍历访问根结点 依次先根遍历根结点的每棵子树 后根遍历依次后根遍历根结点的每棵子树 访问根结点 树没有中序遍历 因子树不分左右 67 讨论 树若采用 先转换 后遍历 方式 结果是否一样 decba abcde bdcea 1 树的先根遍历与二叉树的先序遍历相同 2 树的后根遍历相当于二叉树的中序遍历 3 树没有中序遍历 因为子树无左右之分 结论 树的先根序列 abcde树的后根序列 bdcea 68 先序遍历若森林为空 返回 访问森林中第一棵树的根结点 先根遍历第一棵树的根结点的子树森林 先根遍历除去第一棵树之后剩余的树构成的森林 森林的遍历 为何有中序 深度优先遍历 先序 中序 广度优先遍历 层次 中序遍历若森林为空 返回 中根遍历森林中第一棵树的根结点的子树森林 访问第一棵树的根结点 中根遍历除去第一棵树之后剩余的树构成的森林 69 讨论 若采用 先转换 后遍历 方式 结果是否相同 例如 先序序列 中序序列 ABCDEFGHIJ BCDAFEHJIG 先序序列 中序序列 ABCDEFGHIJ BCDAFEHJIG 结论 森林的先序和中序遍历在两种方式下的结果相同 70 6 5二叉树的典型应用 平衡树 排序树 字典树 判定树 带权树 最优树 由字符串构成的二叉排序树特点 分支查找树 例如12个球如何只称3次便分出轻重 特点 路径带权值 例如长度 是带权路径长度最短的树 又称Huffman树 用途之一是通信中的压缩编码 特点 所有结点左右子树深度差 1 特点 所有结点 左小右大 71 Huffman树概念的引入最佳判定树 什么是带权树 即叶子带有权值 例如 最优二叉树 哈夫曼树 如果是带权路径长度最短的树 73 6 6Huffman树及其应用 一 Huffman树二 Huffman编码 最优二叉树 Huffman树 Huffman编码 带权路径长度最短的树 不等长编码 是通信中最经典的压缩编码 74 树的带权路径长度如何计算 经典之例 WPL WPL WPL Huffman树是WPL最小的树 树中所有叶子结点的带权路径长度之和 36 46 35 75 一 Huffman树 最优二叉树 路径 路径长度 树的路径长度 带权路径长度 树的带权路径长度 Huffman树 由一结点到另一结点间的分支所构成 路径上的分支数目 从树根到每一结点的路径长度之和 结点到根的路径长度与结点上权的乘积 WPL 若干术语 即树中所有叶子结点的带权路径长度之和 带权路径长度最小的树 例如 a e的路径长度 树长度 2 10 Huffman常译为赫夫曼 霍夫曼 哈夫曼 胡夫曼等 WeightedPathLength 76 1 构造Huffman树的基本思想 例 设有4个字符d i a n 出现的频度分别为7 5 2 4 怎样编码才能使它们组成的报文在网络中传得最快 法1 等长编码 如二进制编码 令d 00 i 01 a 10 n 11 则 WPL1 2bit 7 5 2 4 36法2 不等长编码 如Huffman编码 令d 0 i 10 a 110 n 111 则 明确 要实现Huffman编码 就要先构造Huffman树 讨论 Huffman树有什么用 权值大的结点用短路径 权值小的结点用长路径 WPL最小的树 频度高的信息用短码 低的用长码 传输效率肯定高 WPL2 1bit 7 2bit 5 3bit 2 4 35 最小冗余编码 信息高效传输 77 step1 对权值进行合并 删除与替换 在权值集合 7 5 2 4 中 总是合并当前值最小的两个权 先介绍Huffman树的具体构造步骤 a 初始 方框表示外结点 叶子 字符 圆框表示内结点 合并后的权值 b 合并 2 4 c 合并 5 6 d 合并 7 11 谁左谁右 若不规定就会不惟一 78 step2 按左 0 右 1 对Huffman树的所有分支编号 Huffman编码结果 d 0 i 10 a 110 n 111WPL 1bit 7 2bit 5 3bit 2 4 35 小于等长码的WPL 36 特征 每一码不会是另一码的前缀 译码时可惟一复原 Huffman编码也称为前缀码 将Huffman树与Huffman编码挂钩 79 2 构造Huffman树的步骤 即Huffman算法 1 由给定的n个权值 w1 w2 wn 构成n棵二叉树的集合F T1 T2 Tn 即森林 其中每棵二叉树Ti中只有一个带权为wi的根结点 其左右子树均空 2 在F中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树 且让新二叉树根结点的权值等于其左右子树的根结点权值之和 3 在F中删去这两棵树 同时将新得到的二叉树加入F中 4 重复 2 和 3 直到F只含一棵树为止 这棵树便是Huffman树 怎样证明它就是WPL最小的最优二叉树 参考 信源编码 总之 每次合并当前值最小的两个权 此树特征 没有度为1的结点 80 思考 若权值相同 先合并哪个 思考 Huffman编码举例 解 先将概率放大100倍 以方便构造哈夫曼树 放大后的权值集合w 7 19 2 6 32 3 21 10 按哈夫曼树构造规则 合并 删除 替换 可得到哈夫曼树 例1 严题集6 26 假设用于通信的电文仅由8个字母 a b c d e f g h 构成 它们在电文中出现的概率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 试为这8个字母设计哈夫曼编码 如果用0 7的二进制编码方案又如何 类同P148例2 81 例w 2 32 7 6 19 21 3 10 另一种表示 83 重点 如何编程实现Huffman编码 建议1 Huffman树中结点的结构可设计成4或5分量形式 将整个Huffman树的结点存储在一个数组HT 1 n m 中 Huffman树内外结点总数m 2n 1 各叶子结点的编码存储在另一 复合 数组HC 1 n 中 n个权值 叶子将对应n个不同长度的码串 建议2 Huffman树的存储结构大胆采用顺序存储结构 即 先构造Huffman树HT再求出n个权值 字符的Huffman编码HC 参见教材P147 84 m n0 n2 n n 1 2n 1 w 7 19 2 6 32 3 21 10 在机内存储形式为 b c a e g f h 请注意 哈夫曼树样式不惟一 编程时应该有约定 先来先挂接 5 11 17 28 40 60 100 双亲 左右孩子 85 选择parent为0且weight最小的两个结点 根据哈夫曼树得到对应编码 Huffman码的WPL 2 0 19 0 32 0 21 4 0 07 0 06 0 10 5 0 02 0 03 1 44 0 92 0 25 2 61 3 0 19 0 32 0 21 0 07 0 06 0 10 0 02 0 03 3 二进制等长码的WPL 按左0右1标注 86 typedefstruct unsignedintweight 权值分量 可放大取整 unsignedintparent lchild rchild 双亲和孩子分量 HTNode HuffmanTree 用动态数组存储Huffman树 Huffman树的存储表示 双亲 HuffmanTree或HT向量样式 HT 3 parent 9 87 注 常先用一个int型数组来采集权值W 并用 w指针拷贝给HT Huffman树HT的机内实现 先构造Huffman树HT 才能求出N个字符的Huffman编码HC VoidHuffmanCoding HuffmanTree HT HuffmanCode HC int w intn if n 1 return m 2 n 1 n个叶子的HuffmanTree共有2n 1个结点 HT HuffmanTree malloc m 1 sizeof HTNode 0单元未用 for p HT 1 i 1 i n i p w p w 0 0 0 给前n个单元初始化 教材有误 for i m i p p 0 0 0 0 从叶子之后的存储单元清零for i n 1 i m i