数据结构第6章

数据结构 教师 刘琼电话第6章树和二叉树 6 1树的定义和基本术语6 2二叉树6 3遍历二叉树和线索二叉树6 4树和森林 6 5树与等价问题6 6赫夫曼树及其应用 6 7回溯法与树的遍历 6 8树的计数 6 1树的定义和基本术语 数据结构 线性结构和非线性结构线性结构 线性表 栈 队列等 非线性结构 至少存在一个数据元素有不止一个直接前驱或后继 树 图等 树型结构是一类重要的非线性结构 树型结构是结点之间有分支 并且具有层次关系的结构 它非常类似于自然界中的树 6 1树的定义和基本术语 树结构在客观世界是大量存在的 例如家谱 行政组织机构都可用树形象地表示 树在计算机领域中也有着广泛的应用 例如在编译程序中 用树来表示源程序的语法结构 在数据库系统中 可用树来组织信息 在分析算法的行为时 可用树来描述其执行过程等 6 1树的定义和基本术语 1 树型结构实例 1 家族树 6 1树的定义和基本术语 2 书的目录结构 6 1树的定义和基本术语 2 树的定义树 Tree 是n n 0 个结点的有限集 记为T T为空时称为空树 否则它满足以下两个条件 1 有且仅有一个结点没有前驱 称该结点为根结点 Root 6 1树的定义和基本术语 2 除根结点以外 其余结点可分为m m 0 个互不相交的有限集合T0 Tl Tm 1 其中每个集合又构成一棵树 树T0 Tl Tm 1被称为根结点的子树 Subree 每棵子树的根结点有且仅有一个直接前驱 但可以有0个或多个后继 树的逻辑结构表示数据之间的关系是一对多 或者多对一的关系 它的结构特点具有明显的层次关系 是一种十分重要的非线性的数据结构 6 1树的定义和基本术语 图 a 是一棵只有一个根结点的树 图 b 是一棵有12个结点的树 即T A B C K L A是根 除根结点A之外 其余的11个结点分为三个互不相交的集合 T1 T2和T3是根A的三棵子树 且本身又都是一棵树 所以树的定义是递归的 6 1树的定义和基本术语 3 树的基本术语 1 树的结点 包含一个数据元素和指向其子树的所有分支 2 结点的度 一个结点拥有的子树个数 度为零的结点称为叶子结点 3 树的度 树中所有结点的度的最大值Max D I 含义 树中最大分支数为树的度 6 1树的定义和基本术语 4 结点的层次及树的深度 根为第一层 根的孩子为第二层 若某结点为第k层 则其孩子为k 1层 树中结点的最大层次称为树的深度或高度 5 森林 是m m 0 棵互不相的树的集合 森林与树概念相近 相互很容易转换 6 有序树 无序树 如果树中每棵子树从左向右的排列拥有一定的顺序 不得互换 则称为有序树 否则称为无序树 6 1树的定义和基本术语 7 森林 是m m 0 棵互不相交的树的集合 在树结构中 结点之间的关系又可以用家族关系描述 定义如下 8 孩子 双亲 结点子树的根称为这个结点的孩子 而这个结点又被称为孩子的双亲 9 子孙 以某结点为根的子树中的所有结点都被称为是该结点的子孙 6 1树的定义和基本术语 10 祖先 从根结点到该结点路径上的所有结点 11 兄弟 同一个双亲的孩子之间互为兄弟 12 堂兄弟 双亲在同一层的结点互为堂兄弟 6 1树的定义和基本术语 4 树的基本运算树的基本运算主要有 1 初始化操作INITIATE T 创建一棵空树 2 求根函数ROOT T 求树T的根 ROOT X 求结点x所在树的根 3 求双亲函数PARENT T x 在树T中求x的双亲 4 求第i个孩子函数CHILD T x i 在树T中求结点x的第i个孩子 6 1树的定义和基本术语 5 建树函数CRT TREE x F 建立以结点x为根 森林F为子树的树 6 遍历树操作TRAVERSE T 按顺序访问树T中各个结点 6 1树的定义和基本术语 5 树的表示树的逻辑表示方法有多种 常见的有 1 树形图表示法 2 嵌套集合表示法 文氏图表示法 3 凹入表示法 4 广义表表示法 6 1树的定义和基本术语 6 1树的定义和基本术语 6 树的存储结构和线性表一样 树可以用顺序和链式两种存储结构 树的顺序存储结构适合树中结点比较 满 的情况 根据树的非线性结构特点 常用链式存储方式来表示树 树常用的存储方法有 双亲存储表示法 孩子链表表示法和孩子兄弟链表表示法 6 1树的定义和基本术语 1 双亲存储表示法一般采用顺序存储结构实现 用一组地址连续的存储单元来存放树的结点 每个结点有两个域 data域 存放结点的信息 parent域 存放该结点双亲结点的位置特点 求结点的双亲很容易 但求结点的孩子需要遍历整个向量 6 1树的定义和基本术语 6 1树的定义和基本术语 存储结构描述为 defineMaxTreeSize100 定义数组空间的大小typedefcharDataType 定义数据类型typedefstruct DataTypedata 结点数据intparent 双亲指针 指示结点的双亲在数组中的位置 PTreeNode typedefstruct PTreeNodenodes MaxTreeSize intn 结点总数 PTree PTreeT T是双亲链表 6 1树的定义和基本术语 2 孩子链表表示法这是树的链式存储结构 每个结点的孩子用单链表存储 称为孩子链表 n个结点可以有n个孩子链表 叶结点的孩子链表为空表 n个孩子链表的头指针用一个向量表示 特点 与双亲相反 求孩子易 求双亲难 6 1树的定义和基本术语 头指针向量孩子链表 6 1树的定义和基本术语 存储结构描述为 typedefstructCTNode intchild 孩子链表结点structCTNode next ChildPtr typedefstruct 孩子链表头结点 ElemTypedata 结点的数据元素ChildPtrfirstchild 孩子链表头指针 CTBox typedefstruct CTBoxnodes MaxTreeSize intn r 数的结点数和根结点的位置 CTree 6 1树的定义和基本术语 孩子链表表示法的类型说明typedefstructCnode DataType和MaxTreeSize由用户定义 孩子链表结点intchild 孩子结点在数组中对应的下标structCNode next Cnode typedefstruct 孩子链表头结点 DataTypedata 存放树中结点数据CNode firstchild 孩子链表的头指针 PTNode 6 1树的定义和基本术语 typedefstruct PTNodenodes MaxTreeSize Intn root 树的结点数和根结点的位置 Ctree CtreeT T的孩子链表表示 6 1树的定义和基本术语 3 孩子兄弟链表表示法孩子兄弟链表表示法也是树的一种链式存储结构 用二叉链表作为树的存储结构 每个结点的左链域指向该结点的第一个孩子 右链域指向下一个兄弟结点 由于结点中的两个指针指示的分别为 孩子 和 兄弟 故称为 孩子 兄弟链表 这种结构也称为二叉链表 特点 双亲只管长子 长子连接兄弟 6 1树的定义和基本术语 6 1树的定义和基本术语 树的孩子兄弟链表的存储结构描述为 typedefstructCSNode ElemTypedata structCSNode firstchild nextsibling CSNode CSTree 孩子兄弟存储结构的最大优点是可以方便地实现树和二叉树的相互转换和树的各种操作 但是 孩子兄弟存储结构的缺点也是查找当前结点的双亲结点比较麻烦 需要从树根结点开始逐个结点查找 6 2 1二叉树的定义与性质二叉树 BinaryTree 是一种重要的树型结构 是度为2的有序树 它的特点是每个结点至多有两棵子树 和树的定义类似 二叉树的定义也可以用递归形式给出 二叉树 BinaryTree 是n n 0 个结点的有限集 它或者是空集 n 0 或者同时满足以下两个条件 1 有且仅有一个根结点 2 其余的结点分成两棵互不相交的左子树和右子树 6 2二叉树 二叉树与树有区别 树至少应有一个结点 而二叉树可以为空 树的子树没有顺序 但如果二叉树的根结点只有一棵子树 必须明确区分它是左子树还是右子树 因为两者将构成不同形态的二叉树 因此 二叉树不是树的特例 它们是两种不同的数据结构 二叉树有5种基本形态 空二叉树 b 只有根结点的二叉树 c 右子树为空的二叉树 d 左子树为空的二叉树 e 左右子树均不为空的二叉树 两种特殊形态的二叉树 满二叉树和完全二叉树 1 满二叉树 FullBinaryTree 深度为k 且有2k 1个结点的二叉树 特点 1 每一层上结点数都达到最大 2 度为1的结点n1 0 树叶都在最下一层上 结点层序编号方法 从根结点起从上到下逐层 层内从左到右 对二叉树的结点进行连续编号 2 完全二叉树 CompleteBinaryTree 深度为k 结点数为n的二叉树 当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时 称为完全二叉树 完全二叉树的特点 1 每个结点i的左子树的深度Lhi 其结点i的右子树的深度Rhi等于0或1 即叶结点只可能出现在层次最大或次最大的两层上 2 完全二叉树结点数n满足2k 1 1 n 2k 1 3 满二叉树一定是完全二叉树 反之不成立 满二叉树 完全二叉树 LH1 3RH1 1LH1 RH1 2 非完全二叉树非完全二叉树 LH2 0RH2 1LH2 RH2 0 1 1 6 2 2二叉树的性质性质1在二叉树的第i层上至多有2i 1个结点 i 1 性质2深度为k的二叉树至多有2k 1个结点 k 1 深度一定 二叉树的最大结点数也确定 性质3二叉树中 终端结点数n0与度为2的结点数n2存在关系 n0 n2 1性质4结点数为n的完全二叉树 其深度为 log2n l 性质5在按层序编号的n个结点的完全二叉树中 任意一结点i 1 i n 有 i 1时 结点i是树的根 否则 结点i的双亲为结点 i 2 i 1 2i n时 结点i无左孩子 为叶结点 否则 结点i的左孩子为结点2i 2i 1 n时 结点i无右孩子 否则 结点i的右孩子为结点2i 1 6 2 3二叉树的存储结构同线性表一样 二叉树的存储结构也有顺序和链表两种结构 1 顺序存储结构用一组地址连续的存储单元 以层序顺序存放二叉树的数据元素 结点的相对位置蕴含着结点之间的关系 bt 3 的双亲为 3 2 1 即在bt 1 中 其左孩子在bt 2i bt 6 中 其右孩子在bt 2i 1 bt 7 中 这种存储结构适合于完全二叉树 既不浪费存储空间 又能很快确定结点的存放位置 结点的双亲和左右孩子的存放位置 但对一般二叉树 可能造成存储空间的大量浪费 123456789101112ABCDE0000FG0000 一般二叉树也按完全二叉树形式存储 无结点处用0表示 例如 深度为k 且只有k个结点的右单枝树 每个非叶结点只有右孩子 需2k 1个单元 即有2k 1 k个单元被浪费 链式存储结构 二叉链表 设计不同的结点结构 可以构成不同的链式存储结构 常用的有 二叉链表三叉链表线索链表用空链域存放指向前驱或后继的线索 由于二叉树每个结点至多只有2个孩子 分别为左孩子和右孩子 因此可以把每个结点分成三个域 一个域存放结点本身的信息 另外两个是指针域 分别存放左 右孩子的地址 每个结点的结构表示为 其中左链域lchild为指向左孩子的指针 右链域rchild为指向右孩子的指针 数据域data表示结点的值 若某结点没有左孩子或右孩子 其相应的链域为空指针 对应的结构类型定义如下 typedefstructnode ElemTypedata structnode lchild structnode rchild BTree tree 其中 tree是指向根结点的指针 二叉链表的结点结构 二叉链表 说明 一个二叉链表由根指针root唯一确定 若二叉树为空 则root NULL 若结点的某个孩子不存在 则相应的指针为空 具有n个结点的二叉链表中 共有2n个指针域 其中只有n 1个用来指示结点的左 右孩子 其余的n 1个指针域为空 lchilddataparentrchild A C B D E 三叉链表 3 带双亲指针的二叉链表由于经常要在二叉树中寻找某结点的双亲时 可在每个结点上再加一个指向其双亲的指针parent 形成一个带双亲指针的二叉链表 就是三叉链表 三叉链表的结点结构 6 2 4二叉树的基本运算 1 Inittree T 功能 初始化操作 建立一棵空的二叉树 2 Root T 功能 求二叉树的根 3 Parent T x 功能 求二叉树T中值为x的结点的双亲 4 Lchild T x 功能 求结点的左孩子 5 Rchild T x 功能 求结点的右孩子 6 Traverse T 功能 遍历或访问二叉树T 7 creatree T 功能 创建二叉树T 6 3 1遍历二叉树在二叉树的一些应用中 常常要求在树中查找具有某种特征的结点 或者对树中全部结点逐一进行某种处理 这就引入了遍历二叉树的问题 即如何按某条搜索路径访问树中的每一个结点 使得每一个结点仅且仅被访问一次 6 3遍历二叉树和线索二叉树 遍历二叉树 指按一定的规律对二叉树的每个结点 访问且仅访问一次的处理过程 遍历对线性结构是容易解决的 而二叉树是非线性的 因而需要寻找一种规律 使二叉树上的结点能排列在一个线性队列上 从而便于遍历 访问是一种抽象操作 是对结点的某种处理 例如可以是求结点的度 或层次 打印结点的信息 或做其他任何工作 一次遍历后 使树中结点的非线性排列 按访问的先后顺序变为某种线性排列 遍历的次序 假如以L D R分别表示遍历左子树 遍历根结点和遍历右子树 遍历整个二叉树则有DLR LDR LRD DRL RDL RLD六种遍历方案 若规定先左后右 则只有前三种情况 分别规定为 DLR 先 根 序遍历 LDR 中 根 序遍历 LRD 后 根 序遍历 1 遍历方案LDR中序遍历 LRD后序遍历 DLR先序遍历 1 中序遍历二叉树算法思想 若二叉树非空 则 1 中序遍历左子树2 访问根结点3 中序遍历右子树算法描述 voidInorder BiTreebt bt为根结点指针if bt 根非空Inorder bt lchild visit bt data Inorder bt rchild 2 后序遍历二叉树算法思想 若二叉树非空 则 1 后序遍历左子树2 后序遍历右子树3 访问根结点算法描述 voidPostorder BiTreebt bt为根结点指针if bt Postorder bt lchild Postorder bt rchild visit bt data 3 先序遍历二叉树算法思想 若二叉树非空 则 1 访问根结点2 先序遍历左子树3 先序遍历右子树算法描述 voidPreorder BiTreebt bt为根结点指针if bt 根非空visit bt data Preorder bt lchild Preorder bt rchild 例 表达式a b c d e f 遍历结果 中序 a b c d e f后序 abcd ef 先序 a b cd ef 2 遍历算法 1 先序遍历的递归算法如下 假定结点的元素值为字符型 preorder BTree root 前序遍历 if root NULL 如果不是空结点 printf c n root data 输出当前结点值preorder root lchild 递归前序遍历左子结点preorder root rchild 递归前序遍历右子结点 return 结束 2 中序遍历的递归算法如下voidinorder BTree root 中序遍历 if root NULL 如果不是空结点 inorder root lchild 递归中序遍历左子结点printf c n root data 输出当前结点值inorder root rchild 递归中序遍历右子结点 3 后序遍历的算法如下voidpostorder BTree root 后序遍历 if root NULL 如果不是空结点 postorder root lchild 递归后序遍历左子结点postorder root rchild 递归后序遍历右子结点printf c n root data 输出当前结点值 通过上述三种不同的遍历方式得到三种不同的线性序列 从二叉树的遍历定义可知 三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后关系 如果在算法中隐去和递归无关的语句printf 则三种遍历算法是完全相同的 遍历二叉树的算法中的基本操作是访问结点 显然 不论按那种方式进行遍历 对含n个结点的二叉树 其时间复杂度均为O n 6 3 2线索二叉树通过遍历二叉树可得到结点的一个线性序列 在线性序列中 很容易求得某个结点的直接前驱和后继 但是在二叉树上只能找到结点的左孩子 右孩子 结点的前驱和后继只有在遍历过程中才能得到 那么 如何保存遍历二叉树后动态得到的线性序列 以便快速找到某个结点的直接前驱和后继 已知n个结点有n 1个前驱和n 1个后继 一共有2n个链域 其中 n 1个空链域 n 1个指针域 因此 可以用空链域来存放结点的前驱和后继 线索二叉树就是利用n 1个空链域来存放结点的前驱和后继结点的信息 有效利用二叉链表中空的存储空间 指定原有的孩子指针为空的域来存放指向前驱和后继的信息 这样的指针被称为 线索 加线索的过程称为线索化 由此得到的二叉树称作线索二叉树 结点结构在二叉链表中增加ltag和rtag两个标志域 若结点有左子树 则左链域lchild指示其左孩子 ltag 0 否则令左链域指示前驱 ltag 1 若结点有右子树 则右链域rchild指示其右孩子 rtag 0 否则令右链域指示后继 rtag 1 中序 先序和后序线索二叉树中所有实线均相同 所有结点的标志位取值也完全相同 只是当标志位取1时 不同的线索二叉树将用不同的虚线表示 中序遍历得到的线索二叉树称为中序线索二叉树 先序遍历得到的线索二叉树称为先序线索二叉树 后序遍历得到的线索二叉树称为后序线索二叉树 2 整体结构增设一个头结点 令其lchild指向二叉树的根结点 ltag 0 rtag 1 并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继 最后用头指针指示该头结点 线索二叉树的存储结点可描述如下 structnode ElemenTypedata 数据域intltag 左标志域intrtag 右标志域structnode lchild 左指针域structnode rchild 右指针域 BTree 1 已知一棵完全二叉树共有900个结点 试求 树的高度 树中叶子结点个数 树中度为1的结点个数 最后一个非叶子结点是层序遍历序列中的第几个结点 习题 2 设一棵二叉树的先序序列为 中序序列为 试画出该二叉树 习题 3 设有二叉树如下 试对其进行中序线索化 画出相应的中序线索二叉树存储结构示意图 习题 树与二叉树的对应关系树与二叉树均可用二叉链表作为存储结构 因此给定一棵树 用二叉链表存储 可唯一对应一棵二叉树 反之亦然 6 4树和森林 2 树转换成二叉树将一棵树转化为等价的二叉树方法如下 1 在树中各兄弟 堂兄弟除外 之间加一根连线 2 对于任一结点 只保留它与最左孩子的连线外 删去它与其余孩子之间的连线 3 以树根为轴心 将整棵树按顺时钟方向旋转约45 特点 根无右子树应当注意的是 和树对应的二叉树 其左 右子树的概念已改变为 左是孩子 右是兄弟 3 森林转换成二叉树树和森林都可转换成二叉树 但树转换成二叉树后根结点无右分支 而森林转换后的二叉树 其根结点有右分支 将森林转化为二叉树方法如下 1 将森林中的每一棵树转换成等价的二叉树 2 保留第一棵二叉树 自第二棵二叉树始 依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子 当所有的二叉树依此相连后 所得到的二叉树就是由森林转化成的二叉树 3 以树根为轴心 将整棵树按顺时钟旋转约45 4 二叉树转换成森林将当前根结点和其左子树作为森林的一棵树 并将其右子树作为森林的其他子树 重复上面直到某结点的右子树为空 5 树和森林的遍历 1 树的遍历树的遍历可有三条搜索路径 先根 次序 遍历 若树不空 则先访问根结点 然后依次先根遍历各棵子树 后根 次序 遍历 若树不空 则先依次后根遍历各棵子树 然后访问根结点 按层次遍历 若树不空 则自上而下自左至右访问树中每个结点 A B C D E F G H J I K 先根遍历时顶点的访问次序 ABEFCDGHIJK后根遍历时顶点的访问次序 EFBCIJKHGDA层次遍历时顶点的访问次序 ABCDEFGHIJK 2 森林的遍历森林由三部分构成 1 森林中第一棵树的根结点 2 森林中第一棵树的子树森林 3 森林中其它树构成的森林 B C D E F G H J I K 1 先序遍历若森林不空 则访问森林中第一棵树的根结点 先序遍历森林中第一棵树的子树森林 先序遍历森林中 除第一棵树之外 其余树构成的森林 即 依次从左至右对森林中的每一棵树进行先根遍历 2 中序遍历若森林不空 则中序遍历森林中第一棵树的子树森林 访问森林中第一棵树的根结点 中序遍历森林中 除第一棵树之外 其余树构成的森林 即 依次从左至右对森林中的每一棵树进行后根遍历 1 二叉树遍历的应用2 最优二叉树 哈夫曼树 6 5二叉树的应用 1 查找数据元素Search bt x 在bt为二叉树的根结点指针的二叉树中查找数据元素x 查找成功时返回该结点的指针 查找失败时返回空指针 6 5 1二叉树遍历的应用 BiTreeSearch BiTreebt elemtypex 在bt为根结点指针的二叉树中查找数据元素x if bt data x returnbt 查找成功返回 if bt lchild NULL return Search bt lchild x 在bt lchild为根结点指针的二叉树中查找x if bt rchild NULL return Search bt rchild x 在bt rchild为根结点指针的二叉树中查找x returnNULL 查找失败返回 2 统计出给定二叉树中叶子结点的数目 1 顺序存储结构的实现intCountLeaf1 SqBiTreebt intk 一维数组bt 2k 1 为二叉树存储结构 k为二叉树深度 函数值为叶子数 total 0 for i 1 i 2k 1 2 total return total 2 二叉链表存储结构的实现intCountLeaf2 BiTreebt bt为根结点所在链结点的指针 返回值为bt的叶子数 if bt NULL return 0 if bt lchild NULL 3 创建二叉树二叉链表存储 并显示 设创建时 按二叉树带空指针的先序次序输入结点值 结点值类型为字符型 输出按中序输出 CreateBinTree BinTree bt 是以二叉链表为存储结构建立一棵二叉树T的存储 bt为指向二叉树T根结点指针的指针 设建立时的输入序列为 AB0D00CE00F00 建立如下图所示的二叉树存储 voidCreateBinTree BinTree T 以加入结点的先序序列输入 构造二叉链表 charch scanf n c 构造右子树 InOrderOut bt 为按中序输出二叉树bt的结点 voidInOrderOut BinTreeT 中序遍历输出二叉树T的结点值 if T InOrderOut T lchild 中序遍历左子树 printf 3c T data 访问结点的数据 InOrderOut T rchild 中序遍历右子树 main BiTreebt CreateBinTree 4 表达式运算我们可以把任意一个算数表达式用一棵二叉树表示 下图所示为表达式3x2 x 1 x 5的二叉树表示 在表达式二叉树中 每个叶结点都是操作数 每个非叶结点都是运算符 对于一个非叶子结点 它的左 右子树分别是它的两个操作数 对该二叉树分别进行先序 中序和后序遍历 可以得到表达式的三种不同表示形式 前缀表达式 3 xxx 1x5中缀表达式3 x x x 1 x 5后缀表达式3xx x 1x 5 中缀表达式是经常使用的算术表达式 前缀表达式和后缀表达式分别称为波兰式和逆波兰式 它们在编译程序中有着非常重要的作用 1 哈夫曼树的基本概念最优二叉树 也称哈夫曼 Haffman 树 是指对于一组带有确定权值的叶结点 构造的具有最小带权路径长度的二叉树 在许多应用中 常常赋给树中结点一个有某种意义的实数 称此实数为该结点的权 从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度 WPL 6 5 2最优二叉树 哈夫曼树 树中所有叶子结点的带权路径长度之和称为该树的带权路径长度 通常记为 其中Wi为第i个叶结点的权值 li为第i个叶结点的路径长度 n为叶子结点的个数 两结点间的路径 从一结点到另一结点所经过的结点序列 路径长度 路径上的分支数 树的路径长度 从根到每一结点的路径长度之和 如上图所示的二叉树 它的带权路径长度值为 WPL 2 2 4 2 5 2 3 2 28 在给定一组具有确定权值的叶结点 可以构造出不同的带权二叉树 例如 给出4个叶结点 设其权值分别为1 3 5 7 我们可以构造出形状不同的多个二叉树 这些形状不同的二叉树的带权路径长度将各不相同 下图给出了其中4个不同形状的二叉树 它们的带权路径长度分别为 a WPL 1 2 3 2 5 2 7 2 32 b WPL 1 2 3 3 5 3 7 l 33 c WPL 7 3 5 3 3 2 1 1 43 d WPL 1 3 3 3 5 2 7 1 29 由上可见 由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度 那么如何找到带权路径长度最小的二叉树 即哈夫曼树 呢 据哈夫曼树的定义 一棵二叉树要使其WPL值最小 必须使权值越大的叶结点越靠近根结点 而权值越小的叶结点越远离根结点 哈夫曼 Haffman 依据这一特点提出了一种方法 这种方法的基本思想是 1 由给定的n个权值 W1 W2 Wn 构造n棵只有一个叶结点的二叉树 从而得到一个二叉树的集合F T1 T2 Tn 2 在F中选取根结点的权值最小和次小的两棵二叉树作为左 右子树构造一棵新的二叉树 这棵新的二叉树根结点的权值为其左 右子树根结点权值之和 3 在集合F中删除作为左 右子树的两棵二叉树 并将新建立的二叉树加入到集合F中 4 重复 2 3 两步 当F中只剩下一棵二叉树时 这棵二叉树便是所要建立的哈夫曼树 下图给出了一个叶结点权值集合为W 5 10 15 30 40 的哈夫曼树的构造过程 可以计算出其带权路径长度为 WTL 5 10 4 15 3 30 2 40 205 哈夫曼树的结点的度数为0或2 没有度为1的结点 对于同一组给定叶结点所构造的哈夫曼树 树的形状可能不同 但带权路径长度值是相同的 一定是最小的 2 哈夫曼树的构造算法在构造哈夫曼树时 可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息 根据二叉树的性质可知 具有n个叶子结点的哈夫曼树共有2n 1个结点 所以数组HuffNode的大小设置为2n 1 数组元素的结构形式如下 其中 weight域保存结点的权值 lchild和rchild域分别保存该结点的左 右孩子结点在数组HuffNode中的序号 从而建立起结点之间的关系 为了判定一个结点是否已加入到要建立的哈夫曼树中 可通过parent域的值来确定 初始时parent的值为 1 当结点加入到树中时 该结点parent的值为其双亲结点在数组HuffNode中的序号 就不会是 1了 构造哈夫曼树时 首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中 然后根据前面介绍的哈夫曼方法的基本思想 不断将两个小子树合并为一个较大的子树 每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面 下面给出哈夫曼树的构造算法 defineMAXVALUE10000 定义最大权值 defineMAXLEAF30 定义叶子结点个数 defineMAXNODEMAXLEAF 2 1typedefstruct intweight intparent intlchild intrchild HNodeType voidHaffmanTree HNodeTypeHuffNode 哈夫曼树的构造算法 inti j m1 m2 x1 x2 n scanf d 输入叶子结点权值 for i 0 i n 1 i 构造哈夫曼树 m1 m2 MAXVALUE x1 x2 0 for j 0 j n i j if HuffNode j weight m1 将找出的两棵子树合并为一棵子树 HuffNode x1 parent n i HuffNode x2 parent n i HuffNode n i weight HuffNode x1 weight HuffNode x2 weight HuffNode n i lchild x1 HuffNode n i rchild x2 3 哈夫曼编码哈夫曼树的应用很广 哈夫曼编码就是哈夫曼树在电讯通信中的应用之一 通讯中常需要将文字转换成二进制字符串电文进行传送 文字电文 称为编码 收到电文后要将电文转换成原来的文字 电文文字 称为译码 在电报通信中 电文是以二进制的0 1序列传送的 最简单的二进制编码方式是等长编码 假定需传送的电文是CDABB 在电文中仅使用A B C D4种字符 则只需用两个字符串便可分辨 可依次对其编码为 00 01 10 11 上述需发送的的电文是 1011000101 译码员可按两位一组进行译码 恢复原来的电文 例如 需将文字 ABACCDA 转换成电文 文中有四种字符 用2位二进制便可分辨 则文字 ABACCDA 的电文为 00010010101100共14位 译码时 只需每2位一译即可 特点 等长等频率编码 译码容易 但电文不一定最短 采用不等长编码 让出现次数多的字符用短码 则文字 ABACCDA 的电文为 000011010共9位 但无法译码 它既可译为BBCCACA 也可译为AAAACCDA等 采用不等长编码 让出现次数多的字符用短码 且任一编码不能是另一编码的前缀 则文字 ABACCDA 的电文为 0110010101110共13位 设有n种字符 每种字符出现的次数为Wi 其编码长度为Li i 1 2 n 则整个电文总长度为 WiLi 要得到最短的电文 即使得 WiLi最小 也就是以字符出现的次数为权值 构造一棵Huffman树 并规定左分支编码位0 右分支编码为1 则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列 用构造Huffman树设计出来的编码 称为Huffman编码 为了获得传送电文的最短长度 可将字符出现的次数 频率 作为权值赋予该结点 构造一棵WPL最小的哈夫曼树 由此得到的二进制前缀编码就是最优前缀编码 也称哈夫曼编码 可以验证 用这样的编码传送电文可使总长最短 例如 设一文本的字符序列是 DATATRERTERAREAREAART此文本的字符集为 A D T R E 各字符出现的次数为 6 1 4 6 4 以此为权值 构造一棵最优二叉树 哈夫曼树 如下图所示 约定从各非终端结点发出的左分支表示0 右分支表示1 由根结点到叶结点的路径上所有0和1组成的序列 就是该叶结点所表字符的哈夫曼编码 由此可见 根据权值构造哈夫曼树得出的哈夫曼编码 使字符出现次数 频率 与码长呈反比关系 如此得到的电文码长最短 同时 又避免了每一个字符编码是另一个字符编码的前缀 保证了译码的唯一性 下面讨论实现哈夫曼编码的算法 实现哈夫曼编码的算法可分为两大部分 1 构造哈夫曼树 2 在哈夫曼树上求叶结点的编码 求哈夫曼编码 实质上就是在已建立的哈夫曼树中 从叶结点开始 沿结点的双亲链域回退到根结点 每回退一步 就走过了哈夫曼树的一个分支 从而得到一位哈夫曼码值 由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0 1序列 因此先得到的分支代码为所求编码的低位码 后得到的分支代码为所求编码的高位码 我们可以设置一结构数组HuffCode用来存放各字符的哈夫曼编码