《数据结构实用教程(C语言版)》第5章树.ppt

数据结构实用教程 C语言版 中国水利水电出版社 第5章树 本章中主要介绍下列内容 树的逻辑定义和存储结构二叉树的逻辑定义 存储结构二叉树的基本操作算法树和二叉树的转换哈夫曼树及其应用 本章目录 结束 5 1树 5 1 1树的定义5 1 2树的表示方法5 1 3树的基本术语5 1 4树的存储结构 返回到总目录 5 1 1树的定义 树是n n 0 个结点的有限集合 当n 0时称为空树 当n 0时 是非空树 它满足以下两个条件 1 有且仅有一个称为根的结点 2 其余结点分为m m 0 个互不相交的非空集合T1 T2 Tm 其中每个集合本身又是一棵树 称为根的子树 返回到本节目录 树的二元组表示法 树可用二元组来表示 其中 D为结点集合 R为边的集合 一棵树T如图5 1所示 则它的二元组表示方法为 T D R D A B C D E F G H R 图5 1树的逻辑结构图 返回到本节目录 5 1 2树的表示方法 树的逻辑结构表示有树形表示法 文氏图表示法 凹入表示法和广义表表示法等 1 树形表示法这是树的最基本的表示 使用一棵倒置的树表示树结构 图5 1就是采用这种方法 2 文氏表示法使用集合以及集合的包含关系描述树结构 图5 2 a 就是图5 1的树的文氏图表示法 3 凹入表示法使用线段的伸缩关系描述树的结构 图5 2 b 就是图5 1的树的凹入表示法 4 广义表表示法将树的根结点写在括号的左边 除根结点外的其余结点写在括号内并用逗号间隔来描述树的结构 图5 2 c 就是图5 1的树的广义表表示法 返回到本节目录 树的三种表示方法 a 文氏图表示法 b 凹入图表示法 c 广义表表示法图5 2树的其它表示方法 返回到本节目录 5 1 3树的基本术语 1 结点树的结点包含一个数据元素及若干指向其子树的分支 2 结点的度结点所拥有的分支数目或后继结点个数称为该结点的度 Degree 例如图5 1所示的树中结点A的度为3 结点C的度为2 结点E的度为0 3 树的度树中各结点度的最大值称为该树的度 例如图5 1所示的树的度为3 4 叶子 终端结点 度为零的结点称为叶子结点 例如图5 1所示的树中结点E G H I为叶子结点 返回到本节目录 5 1 3树的基本术语 5 分支结点度不为零的结点称为分支结点 例如图5 1所示的树中的A B C D F都是分支结点 6 孩子结点一个结点的后继称为该结点的孩子结点 例如图5 1所示的树中A的孩子结点为B C D 7 双亲结点一个结点称其为其后继结点的双亲结点 例如图5 1所示的树中A是B C D的双亲结点 C是F G的双亲 8 兄弟结点同一双亲结点下的孩子结点互称为兄弟结点 例如图5 1所示的树中B C D互为兄弟结点 F G互为兄弟结点 但不同双亲的两个同层结点不互为兄弟结点 如G和H不互为兄弟结点 返回到本节目录 5 1 3树的基本术语 9 堂兄弟双亲互为兄弟的两个结点互称为堂兄弟 例如图5 1所示的树中G和H就互为堂兄弟 10 子孙结点一个结点的所有子树中的结点称之为该结点的子孙结点 例如图5 1所示的树中A的子孙为B C D E F G H I 11 祖先结点从树根结点到达一个结点的路径上的所有结点称为该结点的祖先结点 例如图5 1所示的树中E的祖先结点为A和B 包括其双亲结点B 返回到本节目录 5 1 3树的基本术语 12 层数树的根结点的层数为1 其余结点的层数等于它双亲结点的层数加1 例如图5 1所示的树中A的层数为1 B C D的层数为2 E F G H的层数为3 I的层数为4 13 树的深度树中结点的最大层数称为树的深度 或高度 例如图5 1所示的树中的深度为4 14 有序树和无序树如果一棵树中的结点的各子树从左到右是有次序的 即若交换了某结点各子树的相对位置 则构成了不同的树 称这样的树为有序树 反之 则为无序树 15 森林m m 0 棵互不相交树的集合称为森林 返回到本节目录 5 1 4树的存储结构 1 双亲表示法用一个一维数组存储树中的各个结点 数组元素是一个结构体型数据 包含两个域 data域和parent域 分别表示结点的数据值和其双亲结点在数组中的下标 其类型定义如下 typedefstruct ElemTypedata 结点的数据域 ElemType可以是任意类型 intparent 结点存储其双亲的数组下标值 ParType MaxSize 返回到本节目录 1 双亲表示法示例 图5 1中给出的树 可以用图5 3来存储表示 其中 规定数组下标为0的位置存储的是根结点 设根结点的parent域为 1 图5 3图5 1中树的双亲表示法 返回到本节目录 5 1 4树的存储结构 2 孩子表示法将每个结点的孩子结点构成一个单链表 称之为孩子链表 n个结点的树有n个这样的孩子链表 为了方便起见 我们将每个结点存放在一个顺序表中 顺序表的每个元素有两个域 一个是存放该结点的数据值 另一个是存放该结点的第一个孩子的地址 孩子结点也有两个域 一个域是存放该孩子结点在顺序表中的位置 数组下标 另一个域是存放下一个孩子的地址 返回到本节目录 2 孩子表示法举例 图5 4是图5 1所示树的孩子表示法 其中 规定表头下标为0的位置存放根结点 图5 4图5 1树的孩子表示法 返回到本节目录 5 1 4树的存储结构 3 孩子兄弟法孩子兄弟法存储结构是一种二叉链表 链表中每个结点包括三个域 数据值和两个指针 其中一个指针指向该结点的最左边第一个孩子 而另一个指针则指向该结点的下一个兄弟 每个结点的类型定义如下 typedefstructnode2 ElemTypedata 数据域 Structnode2 child brother 其第一个孩子和其右边兄弟的地址 CBNodeType 孩子兄弟结点类型 返回到本节目录 图5 5是图5 1所示树的孩子兄弟表示法的存储结构 其中T指向树的根结点 图5 5图5 1树的孩子兄弟表示法 返回到本节目录 5 2二叉树 5 2 1二叉树的定义5 2 2二叉树的性质5 2 3二叉树的存储结构5 2 4二叉树的基本运算 返回到总目录 5 2 1二叉树的定义 1 二叉树的定义二叉树 BinaryTree 是有n n 0 个结点的有限集合 1 该集合或者为空 n 0 2 或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树 3 左子树和右子树同样又都是二叉树 返回到本节目录 5 2 1二叉树的定义 2 二叉树的形态二叉树归纳起来有五种形态 如图5 7所示 a 空二叉树 b 只有一个根结点 c 右子树为空 d 左子树为空 e 左 右子树非空图5 7二叉树的五种形态 返回到本节目录 5 2 2二叉树的性质 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 性质2 深度为k的二叉树中至多有2k 1个结点 性质3 对任意一棵二叉树T 如果其叶子结点数为n0 度为2的结点数为n2 则有n0 n2 1 返回到本节目录 5 2 2二叉树的性质 下面介绍两种特殊的二叉树 1 满二叉树一棵深度为k 且有2k 1个结点的二叉树称为满二叉树 图5 9 a 所示是一棵深度为4的满二叉树 其特点是每一层上的结点都具有最大的结点数 2 完全二叉树在一棵二叉树中 除最后一层外 若其它层都是满的 并且最后一层或者是满的 或者是在右边缺少连续的若干个结点 则称此二叉树为完全二叉树 据此得知满二叉树是完全二叉树的特例 图5 9 b 是一棵深度为4的完全二叉树 返回到本节目录 满二叉树和完全二叉树示例 a 一棵满二叉树 b 一棵完全二叉树图5 9一棵满二叉树和一棵完全二叉树示意图 返回到本节目录 5 2 2二叉树的性质 性质4 具有n个结点的完全二叉树的深度为 性质5 如果一棵有n个结点的完全二叉树 其深度为 的结点按层次 从第1层到第层 每层从左到右 则对任一结点i 1 i n 有 1 如果i 1 结点i是根结点 无双亲 如果i 1 则其双亲结点是结点i 2 2 如果2i n 则结点i无左孩子 该结点为叶子结点 否则其左孩子是结点2i 3 如果2i 1 n 则结点i无右孩子 该结点为叶子结点 否则其左孩子是结点2i 1 返回到本节目录 5 2 3二叉树的存储结构 1 顺序存储结构顺序存储一棵二叉树时 先对该二叉树中的各结点进行编号 然后以各结点的编号为下标 把各结点的值存到一维数组中 其编号过程为 首先 把树的根结点的编号定为1 然后按照层次从上到下 从左到右的顺序对每一结点进行编号 当一个结点的双亲结点的编号为i时 若它是左孩子 则编号为2i 若它是右孩子 则编号为2i 1 如图5 10 a 所示的二叉树 各结点上方的数字就是该结点的编号 对应的顺序存储结构为图5 10 b 所示 返回到本节目录 顺序存储的二叉树示例 一棵带编号的二叉树 b 对应的顺序存储结构图5 10一棵二叉树及其顺序存储结构 返回到本节目录 5 2 3二叉树的存储结构 2 链式存储结构对于一般的二叉树 通常采用二叉链表示 链表中的每个结点包含两个指针 分别指向该结点的左孩子和右孩子 在二叉树的链式存储结构中 结点的类型定义如下 Typedefstructtnode ElemTypedata 数据域 structtnode lchild rchild 左 右孩子指针域 BTNode 二叉树结点存储类型 其中 data域中存入结点的数据值 lchild和rchild分别表示左指针域和右指针域 分别存储其左 右孩子结点的地址 返回到本节目录 图5 11二叉树链式存储结构 如图5 10的二叉树链式存储结构如图5 11所示 返回到本节目录 5 2 4二叉树的基本运算 二叉树的常用运算有以下几种 1 bt CreateBTree str 根据二叉树的广义表表示法str建立二叉树bt 2 BTHeight bt 求一棵二叉树bt的高度 3 NodeCount bt 求一棵二叉树bt的结点个数 4 LeafCount bt 求一棵二叉树bt的叶子结点个数 5 DispBTree bt 以广义表表示法输出一棵二叉树bt 返回到本节目录 5 3二叉树的建立和遍历 5 3 1二叉树的建立和输出5 3 2二叉树的遍历5 3 3由遍历序列恢复二叉树 返回到总目录 5 3 1二叉树的建立和输出 1 二叉树的建立二叉树的建立是二叉树的重要运算之一 我们介绍的方法是 用字符ch扫描用广义表表示法输入的二叉树的字符串str 分以下几种情况 1 若ch 则将前面刚创建的结点作为双亲结点进栈 并置k 1 表示其后创建的结点将作为这个结点的左孩子结点 2 若ch 表示栈中结点的左右孩子结点处理完毕 退栈 3 若ch 表示要创建一个结点 并根据k值建立它与栈中结点之间的联系 当k 1时 表示这个结点作为栈中结点的左孩子结点 当k 2时 表示这个结点作为栈中结点的右孩子结点 如此循环直到str处理完毕 算法中使用一个栈st保存双亲结点 top为其栈顶指针 k指定其后处理的结点是双亲结点 保存在栈中 的左孩子结点 k 1 还是右孩子结点 k 2 返回到本节目录 1 二叉树的建立 1 二叉树的存储结构及相关类型的定义如下 defineNULL0 定义空指针为0 defineMaxSize100 树的最大元素个数为100 typedefcharElemType 重定义char为ElemType类型 typedefstructtnode ElemTypedata 数据域 structtnode lchild rchild 左 右孩子指针 BTNode 二叉树结点类型 返回到本节目录 1 二叉树的建立算法 2 二叉树的建立对应的算法如算法5 1所示 算法5 1BTNode CreateBTree char str BTNode bt st MaxSize p NULL inttop 1 k j 0 charch bt NULL ch str j while ch 0 switch ch case top 若是左括号 则先入栈 st top p k 1 break case top break 若是右括号 则出栈 返回到本节目录 1 二叉树的建立算法 case k 2 break 若是逗号 则有右子树 default 若是其它字符 则生成新的二叉树结点 p BTNode malloc sizeof BTNode p data ch p lchild p rchild NULL if bt NULL bt p else switch k case1 st top lchild p break case2 st top rchild p break j ch str j return bt 返回到本节目录 5 3 1二叉树的建立和输出 2 用广义表表示法输出二叉树其过程是 对于非空二叉树bt 先输出其元素值 当存在左孩子结点或右孩子结点时 输出一个 符号 然后递归处理左子树 输出一个 符号 递归处理右子树 最后输出一个 对应的算法如算法5 2 返回到本节目录 2 用广义表表示法输出二叉树 算法5 2voidDispBTree BTNode bt if bt NULL printf c bt data if bt lchild NULL printf DispBTree bt lchild if bt rchild NULL printf DispBTree bt rchild printf 返回到本节目录 5 3 2二叉树的遍历 一棵二叉树由根结点 D 根结点的左子树 L 和根结点的右子树 R 三部分组成 一般限定先左后右的次序 那么只有三种遍历 DLR 根左右 LDR 左根右 LRD 左右根 我们将这三种遍历方法称作前 根 序遍历 中 根 遍历和后 根 序遍历 也可以对二叉树的每个层次的各结点按从左至右进行遍历 按层次遍历 下面我们分别介绍这几种遍历方法 返回到本节目录 1 前 根 序遍历二叉树 DLR 有些教材称为先 根 序遍历 若二叉树为空 遍历结束 否则依次执行以下操作 1 访问根结点 2 前序遍历根结点的左子树 3 前序遍历根结点的右子树 前序遍历的递归算法如算法5 3所示 以图5 10为例 进行前序遍历的输出序列为 ABDCEGF 返回到本节目录 前序遍历的递归算法 算法5 3voidPreOrder BTNode bt 前序遍历二叉树BT if bt NULL return 递归调用的结束条件 else printf c bt data 输出结点的数据域 PreOrder bt lchild 前序递归遍历左子树 PreOrder bt rchild 前序递归遍历右子树 返回到本节目录 2 中 根 序遍历二叉树 LDR 若二叉树为空 遍历结束 否则依次执行以下操作 1 中序遍历根结点的左子树 2 访问根结点 3 中序遍历根结点的右子树 中序遍历的递归算法如算法5 4所示 以图5 10为例 进行中序遍历的输出序列为 DBAGECF 返回到本节目录 中序遍历的递归算法 算法5 4voidInOrder BTNode bt 中序遍历二叉树BT if bt NULL return 递归调用的结束条件 else InOrder bt lchild 中序递归遍历左子树 printf c bt data 输出结点的数据域 InOrder bt rchild 中序递归遍历右子树 返回到本节目录 3 后 根 序遍历二叉树 LRD 若二叉树为空 遍历结束 否则依次执行以下操作 1 后序遍历根结点的左子树 2 后序遍历根结点的右子树 3 访问根结点 后序遍历的递归算法如算法5 5所示 以图5 10为例 进行后序遍历的输出序列为 DBGEFCA 返回到本节目录 后序遍历的递归算法 算法5 5voidPostOrder BTNode bt 后序遍历二叉树BT if bt NULL return 递归调用的结束条件 else PostOrder bt lchild 后序递归遍历左子树 PostOrder bt rchild 后序递归遍历右子树 printf c bt data 输出结点的数据域 返回到本节目录 4 层次遍历二叉树 在进行层次遍历时 对某一层的结点访问完后 再按照它们的访问次序对各个结点的左 右孩子顺序访问 这样一层一层进行 先访问的结点其左 右孩子也要先访问 这样的操作与队列的原则比较符合 所以可以用一个环形队列qu来实现 层次遍历过程是先将根结点进队 在队不空时循环 从队列中出列一个结点 p 访问它 若它有左孩子结点 将左孩子结点进队 若它有右孩子结点 将右孩子结点进队 直到队空为止 算法如算法5 6所示 以图5 10为例 进行按层次遍历的输出序列为 ABCDEFG 返回到本节目录 层次遍历的算法 算法5 6voidLevelOrder BTNode bt BTNode p BTNode qu MaxSize 定义循环队列 存放结点指针 intfront rear 定义队头队尾指针 front rear 1 空队 rear qu rear bt 根结点指针进入队列 返回到本节目录 层次遍历的算法 while front rear 队列不空时 front front 1 MaxSize p qu front 队头出队列 printf c p data if p lchild NULL 有左孩子时将其进队 rear rear 1 MaxSize qu rear p lchild if p rchild NULL 有右孩子时将其进队 rear rear 1 MaxSize qu rear p rchild 返回到本节目录 5 3 3由遍历序列恢复二叉树 1 由前序和中序恢复二叉树 1 根据前序序列确定树的根 第一个结点 根据中序序列确定左子树和右子树 2 分别找出左子树和右子树的根结点 并把左 右子树的根结点联到双亲结点上去 3 再对左子树和右子树按此法找根结点和左 右子树 直到子树只剩下1个结点或2个结点或空为止 返回到本节目录 5 3 3由遍历序列恢复二叉树 2 由中序和后序恢复二叉树由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树 其方法为 1 根据后序序列找出根结点 最后一个 根据中序序列确定左 右子树 2 分别找出左子树和右子树的根结点 并把左 右子树的根结点联到双亲 parent 结点上去 3 再对左子树和右子树按此法找根结点和左 右子树 直到子树只剩下1个结点或2个结点或空为止 返回到本节目录 5 4树 森林与二叉树的转换 5 4 1树 森林转换为二叉树5 4 2二叉树还原为树 森林 返回到总目录 5 4 1树 森林转换为二叉树 1 树转换成二叉树将一棵树转换成二叉树的过程如下 1 加线 树中所有相邻兄弟之间加一条连线 2 抹线 对树中的每个结点 只保留它与第一个孩子结点之间的连线 删除它与其它孩子结点之间的连线 3 旋转 以树的根结点为轴心 将整棵树顺时针旋转45 使之成为二叉树 返回到本节目录 例5 3 将图5 15 a 所示的树转换成二叉树 转换过程如图5 15 b c d 所示 a 原始树 b 相邻兄弟之间加连线 虚线 c 删除与双亲结点的连线 d 转换之后的二叉树图5 15一棵树转换成二叉树的过程 返回到本节目录 2 森林转换为二叉树 将森林转换为二叉树的过程如下 1 将森林中的每一棵树转换成相应的二叉树 2 第一棵二叉树保持不动 从第二棵二叉树开始 依次把后一棵二叉树作为前一棵二叉树根结点的右子树 直到把最后一棵二叉树作为其前一棵二叉树的右子树为止 此时所得到的二叉树就是由森林转换得到的二叉树 返回到本节目录 例5 4 将图5 16 a 所示的森林转换成二叉树 解 转换的过程如图5 16 b 5 16 e 所示 a 森林 b 相邻兄弟加连线 虚线 c 删除与双亲结点的连线 d 每棵树转换成二叉树 返回到本节目录 例5 4 e 所有的二叉树连接成一棵二叉树图5 16森林转换成二叉树的过程 返回到本节目录 5 4 2二叉树还原为树 森林 1 二叉树还原为树二叉树还原为树的过程如下 1 加线 如果某结点的左孩子有右子树 在该结点和其左孩子的右子树的右分支上各结点间加线 2 抹线 抹掉各结点的右子树的右分支取上的连线 3 旋转整理得到树 返回到本节目录 5 4 2二叉树还原为树 森林 2 二叉树还原为森林二叉树还原为森林的过程如下 1 连线 若某结点是其双亲的左孩子 则把该结点的右孩子 右孩子的右孩子 都与该结点的双亲结点用连线连起来 2 抹线 删除原二叉树中原来双亲结点与右孩子结点的连线 3 整理由 1 2 两步所得到的树或森林 使之结构层次分明 返回到本节目录 5 5哈夫曼树 5 5 1相关概念和哈夫曼树的定义5 5 2哈夫曼树的构造方法5 5 3哈夫曼编码 返回到总目录 5 5 1相关概念和哈夫曼树的定义 1 路径树中一个结点与另一个结点之间的分支构成这两个结点之间的路径 树中不是每对结点之间都有路径 如兄弟结点之间就无路径 而从根结点到树中任一结点都存在一条路径 2 路径长度树中路径上的分支数目 3 树的路径长度根结点到树中每个结点的路径长度之和 4 结点的权值所谓权值是人们根据需要为每个叶子结点赋予的一个数值 返回到本节目录 5 结点的带权路径长度是指从树根到该结点之间的路径长度与结点的权值的乘积 6 树的带权路径长度树中所有叶子结点的权值乘以该结点的路径长度之和 用公式可以表示为 其中 wk为第k个叶子结点的权值 lk是从根结点到第k个叶子结点的路径长度 7 哈夫曼树哈夫曼树又称为最优二叉树 它是n个带权值的叶子结点所构成的所有二叉树中带权路径长度WPL最小的二叉树 返回到本节目录 求不同二叉树的WPL 如图5 19 a b c 所示的三棵二叉树 它们的带权路径长度分别为 a WPL 2 2 3 2 4 2 6 2 30 b WPL 2 3 3 3 4 2 6 1 29 c WPL 4 3 6 3 3 2 2 1 38 a b c 图5 19相同叶子结点所构成的不同带权路径长度的二叉树 返回到本节目录 5 5 2哈夫曼树的构造方法 下面介绍哈夫曼树的构造方法 步骤如下 1 将给定的n个权值 w1 w2 wn 作为n个根结点的权值构造一个具有n棵二叉树的森林 T1 T2 Tn 其中每棵二叉树只有一个根结点 2 在森林中选取两棵树根结点的权值最小的二叉树作为左右子树构造一棵新二叉树 新二叉树的根结点的权值为原来两棵树根结点的权值之和 3 在森林中 将上面选择的这两棵根结点的权值最小的二叉树从森林中删除 并将最新构造的二叉树加入到森林中 4 重复上面 2 和 3 直到森林中只有一棵二叉树为止 这棵二叉树就是哈夫曼树 返回到本节目录 例5 7 假设有一组权值 2 3 7 8 12 9 6 19 下面我们将利用这组权值演示构造哈夫曼树的过程 解 第一步 以这8个权值作为根结点的权值构造具有8棵树的森林 第二步 从中选择两个根的权值最小的树2 3作为左右子树构造一棵新树 并将这两棵树从森林中删除 并将新树5添加进去 返回到本节目录 第三步 重复第二步过程 直到森林中只有一棵树为止选择5 6 将11放回 选择7 8 将15放回 返回到本节目录 选择9 11 将20放回 选择12 15 将27放回 返回到本节目录 选择19 20 将39放回 选择27 39 最后森林中只有一棵树 结束操作 这棵树就是哈夫曼树 返回到本节目录 为了实现构造哈夫曼树的算法 设计哈夫曼树中每个结点类型如下 typedefstruct chardata 结点值 intweight 权值 intparent 双亲结点下标 intlchild 左孩子结点下标 intrchild 右孩子结点下标 HTCode 哈夫曼树结点类型 返回到本节目录 用ht数组存放哈夫曼树 对于具有n个叶子结点的哈夫曼树 总共有2n 1个结点 其算法思路是 n个叶子结点只有data和weight域值 先将所有2n 1个结点的parent lchild和rchild域置为 1 处理每个非叶子结点ht i 存放在ht n ht 2n 2 中 从ht 0 ht i 2 中找出根结点 即其parent域为 1 最小的两个结点ht lnode 和ht rnode 将它们作为ht i 的左右子树 ht lnode 和ht rnode 双亲结点置为ht i 并且ht i weight ht lnode weight ht rnode weight 如此这样直到所有的n 1个非叶子结点处理完毕 构造哈夫曼树的算法如算法5 7 返回到本节目录 算法5 7voidCreateHT HTCodeht intn inti j k lnode rnode intmin1 min2 for i 0 i 2 n 1 i 将双亲 左 右孩子域置初值 1 ht i parent ht i lchild ht i rchild 1 for i n i 2 n 1 i min1 min2 32767 两个最小值置初值为系统最大值 lnode rnode 1 返回到本节目录 for k 0 kht k weight min1 ht k weight 找出最小的权值 lnode k 最小权值的结点下标值 for k 0 kht k weight 次最小权值的结点下标值 返回到本节目录 ht lnode parent i ht rnode parent i ht i weight ht lnode weight ht rnode weight ht i lchild lnode ht i rchild rnode 返回到本节目录 5 5 3哈夫曼编码 1 什么是哈夫编码 在进行快速远距离的通信时 经常需要将传送的文字转换成由二进制字符0 1组成的二进制代码 称之为编码 如果在编码时考虑字符出现的频率 让出现频率高的字符采用尽可能短的编码 出现频率低的字符采用稍长的编码 构造一种不等长编码 则电文的代码就可能更短 哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案 返回到本节目录 5 5 3哈夫曼编码 2 生成哈夫曼编码的方法要设计长短不同的编码 首先要做到不同字符的编码不会混淆 即任一个字符的编码都不是另一个字符的编码的前缀 即不是另一个字符编码的开头一部分 满足这个条件的编码叫做前缀编码 即前缀编码是指所编码的字符可以通过前缀唯一地正确识别并译出 利用哈夫曼树就可以方便的设计 返回到本节目录 2 生成哈夫曼编码的方法 1 构造哈夫曼树设需要编码的字符集合为 d1 d2 dn 它们在电文中出现的次数集合为 w1 w2 wn 以d1 d2 dn作为叶子结点 w1 w2 wn作为它们的权值 构造一棵哈夫曼树 2 在哈夫曼树上求叶结点的编码 规定哈夫曼树中的左分支代表0 右分支代表1 则从根结点到每个叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码 返回到本节目录 例5 8 设有A B C D E F6个字符 其出现的频度分别为0 06 0 02 0 04 0 03 0 07 0 12 试设计它们的哈夫曼编码 解 将所有频度全部乘以100 得到各字符的权值 6 2 4 3 7 12 根据这组权值构造的哈夫曼树如图5 21所示 并设哈夫曼树的每个左分支为0 右分支为1进行编码 返回到本节目录 则得到各个字符的哈夫曼编码为 A 00B 1010C 100D 1011E 01F 11 图5 21哈夫曼编码树 返回到本节目录 3 哈夫曼编码的算法实现 1 设计哈夫曼编码的数据类型如下 typedefstruct charcd N 存放当前结点的哈夫曼编码 intstart start指向cd数组中的哈夫曼编码最开始字符 HCode 哈夫曼编码存放类型 返回到本节目录 3 哈夫曼编码的算法实现 2 生成哈夫曼编码的算法由于哈夫曼树中的每个叶子结点的哈夫曼编码长度不同 为此采用HCode类型变量的cd start cd n 存放当前结点的哈夫曼编码 只需对叶子结点求哈夫曼编码 对于当前叶子结点ht i 先将对应的哈夫曼编码和hcd i 的start域置初值n 找其双亲结点ht