数据结构第6章.ppt

第6章树形结构 6 1树形结构的基本概念6 2二叉树的基本概念和性质6 3二叉树的存储结构6 5二叉树的遍历6 8树与森林6 10树的应用示例 哈夫曼树 6 1 1树结构的定义 数据对象D n个数据元素的有穷集合 n 0 数据关系R n 0时 称为空树 n 0时 它满足以下条件 1 有且仅有一个结点d0 D 满足 不存在任何d D 使 R 我们称它为树的根 Root 2 除根结点d0外 D上每个结点d 若有的话 总存在一个唯一的结点d D d d 使得 R 3 若T d0 非空 则T d0 可分成m个 m 0 不相交的集合T1 T2 Tm 而且这些集合中的每一个又都是满足本定义的树 称作T的子树 subTree 若T d0 为空 称T无子树 或子树为空 递归定义 6 1树结构的基本概念 树形结构示例及相关术语 A B C D E F G I J Level1 Level2 Level3 Level4 Depth 4 A b c a 分支 Branch 结点之间的二元关系 入度 InDegree x的前驱的个数称为x的入度 结点 Node 数据元素 若干个指向子树的分支 度 Degree 出度 OutDegree 结点拥有的子树 后继 的个数称为该结点的度 也称为出度 树的度 树中所有结点的度的最大值叶子结点 LeafNode 无后继 子树 的结点称为叶子 分支结点 BranchNode 有后继的结点称为分枝结点 层次 Level 根为第1层 对任何其它结点 若它父亲为第k层结点 则它为第 k 1 层结点 层号为k 1 儿子结点 Sons 双亲 父亲 Parents 祖先 Ancestor 后代 Descendants 兄弟 Brothers 堂兄弟 Cousin 深度 depth 树中的具有最大层号的结点的层号 称为树的深度 高度 祖辈 上层 Forerunner 层号比结点x小的结点 称为x的祖辈 上层 后辈 下层 Latecomes 层号比结点x大的结点 称为x的后辈 下层 森林 Forest 相互m m 0 不相交的树的集合称为森林 反过来树也可以有森林来定义 任何一棵非空树是一个二元组Tree root F root为根结点 F为子树森林有序树 子树的次序不能互换无序树 子树的次序可以互换 线性结构与树形结构比较 线性结构第一个数据元素 无前驱 最后一个数据元素 无后继 其它数据元素 一个前驱 一个后继 树形结构根结点 无前驱 多个叶子结点 无后继 其它结点 一个前驱 多个后继 6 2二叉树的概念 该集合或者为空 或者是由一个根结点加上两棵分别称为左子树和右子树的 互不相交的二叉树组成 左子树 右子树 左子树 右子树 a b c d e 五种二叉树的基本形态 6 2 2几种特殊二叉树 下面介绍几种特殊结构的二叉树 它们在实际中有许多应用 这几种特殊二叉树是逻辑结构上的特殊二叉树 在后面的章节中 我们还将介绍几种语义上的特殊二叉树 1 满二叉树 只含度为0与度为2的结点 且度为0的结点只出现在最后一层的二叉树称为满二叉树 实例见图6 3 a 2 顺序二叉树 对任一棵满二叉树 从它的最后一层的最右结点起 按从下到上 从右到左的次序 去掉若干个结点后所成的树称为顺序二叉树 实例见图6 3 b 3 完全二叉树 不含度为1的结点的二叉树称完全二叉树 显然 与满二叉树的不同是 完全二叉树的度为0的结点可出现在任一层上 实例见图6 3 c d 4 平衡二叉树若树中任一结点的任两个子树的高度之差不超过1 则称这种树为平衡树 特别是对二叉树 则为平衡二叉树 实例见图6 3 f a 满二叉树 b 顺序二叉树 d 顺序 完全二叉树 e 平衡二叉树 f 一般二叉树 非平衡 c 完全二叉树 图6 3特殊二叉树示例 定理6 1若二叉树的层次从1开始 则在二叉树的第i层最多有2i 1个结点 i 0 证明 i 1时 有2i 1 20 1 成立假定 i k时性质成立 当i k 1时 第k 1的结点至多是第k层结点的两倍 即总的结点个数至多为2 2k 1 2k故命题成立 合并了书中的定理6 1和6 2 6 2 3二叉树的基本性质 定理6 3高度为k的二叉树最多有2k 1个结点 k 1 证明 仅当每一层都含有最大结点数时 二叉树的结点数最多 利用性质1可得二叉树的结点数至多为 20 21 22 23 2k 1 2k 1合并书中定理6 3和6 4 定理6 5 对任一棵二叉树 有n0 n2 1n 2n0 n1 1这里 n0 n1和n2分别为度为0 1和2的结点的数目 n表示结点总数 证 显然 n n0 n1 n2另一方面 由于二叉树除根外每个结点恰好有一个前趋 所以 非根结点恰与分枝一一对应 故有n B 1这里 B为分枝数目 又分枝是由度为1和2的结点射出的 故有B n1 2n2结合上面三式 即可导出n0 n2 1与n 2n0 n1 1 定理6 6具有n个结点的顺序二叉树 的高度为 log2n 1 在其他书籍 此定理中的顺序二叉树为完全二叉树 定理6 7 若对一棵顺序二叉树的结点按层序编号 即从根所在层起 依次从层号较小的层到层号较大的层 同层从左到右 给各结点依次编以连续的号码 则对任一结点i 1 i n n为结点数目 1为根的编号 有 a 若i 1 则结点i是根 无父亲 若i 1 则其父亲的编号为 i 2 b 若2i n 则结点i无左儿子 从而也无右儿 为叶子 否则i的左儿子的编号为2i c 若2i 1 n 则结点i无右孩子 否则它的右孩子结点的编号为2i 1 6 2 4二叉树的遍历的概念 遍历 顺着某一条搜索路径巡防二叉树中的结点 使得每个结点均被访问一次 而且仅被访问一次 访问 的含义很广泛 如 输出结点中的信息等 遍历 是任何类型数据结构均有的操作 对线性结构而言 只有一条搜索路径 因为每个结点只有一个后继 故不需要特别地讨论 而二叉树的每个结点可能有两个后继 则存在选择何种路径来遍历所有结点的问题 搜索路径 对 二叉树 而言 有三条搜索路径 1 现上后下的按层次遍历2 先左 子树 后右 子树 的遍历3 先右 子树 后左 子树 的遍历 先左后右的遍历算法 先 根 序遍历中 根 序遍历后 根 序遍历按层次遍历层序遍历 前序遍历 前序遍历二叉树算法 若二叉树为空 则空操作 否则访问根结点 V 前序遍历左子树 L 前序遍历右子树 R 前序遍历结果 1245367中序遍历结果 2541376后序遍历结果 5427631层序遍历结果 1234657 图6 0二叉树遍历示例 中序遍历二叉树算法 若二叉树为空 则空操作 否则中序遍历左子树 L 访问根结点 V 中序遍历右子树 R 后序遍历二叉树算法 若二叉树为空 则空操作 否则后序遍历左子树 L 后序遍历右子树 R 访问根结点 V 二叉树遍历 前序 中序和后序遍历都是采用递归的方式定义和实现 层序遍历层序遍历是按树的层序编号的次序访问各结点 即按从上层到下层 同层内从左到右的次序访问结点 层序遍历二叉树算法是若二叉树为空 则空操作 否则 根结点进队如队列不空 循环 将队首结点的左右孩子入队 队首出队 最后 出队序列就是层序遍历序结果 6 3二叉树的存储结构 6 3 1顺序存储结构 顺序二叉树的顺序存储结构这种存储结构是按结点的层序编号的次序 将结点存储在一片连续存储区域内 结点的相对地址与编号之间的换算 有下列关系 结点相对地址 结点编号 1 每个结点所占单元数目 A C B 1 2 4 3 5 7 6 8 9 10 数组下标0123456789 一般二叉树的顺序存储对一般的二叉树而言 则需在该二叉树中补设一些虚结点 使它成为一棵顺序二叉树 然后对结点按层序编号 这种存储方式中 实结点是不连续出现的 所以 若虚结点对应的存储位置不能被利用 则是一种很大的浪费 虚结点数目可能很大 a b c 12345679 axbxxxc 图 一般二叉树的连续存储 x表示虚结点的位置 6 3 2链式存储 所谓二叉树的链式存储结构是指 用链表来表示一棵二叉树 即用链来指示着元素的逻辑关系 常用的两种形式 二叉表 二指针式 三叉表 三指针式 二叉表 结点的存储的结构为 a 带头指针的二叉链表 b 带头结点的二叉链表 三叉表 结点的存储的结构为 三叉链表表示示意图 6 4二叉树对象模型 二叉树的存储结构是 二叉表二叉树的基本操作 1 创建二叉树2 二叉树的遍历 前序遍历 中序遍历 后序遍历和层序遍历 3 删除二叉树 二叉树的对象描述 templateclassTBinTree public TBinTreeNode root longnumNodes TBinTree TBinTree virtualvoidpreCreateBinTree TBinTreeNode r virtualvoidpreTraverse TBinTreeNode r virtualvoidpreTraverse stack TBinTreeNode r virtualvoidinTraverse TBinTreeNode r virtualvoidpostTraverse TBinTreeNode r virtualvoidlevelTraverse TBinTreeNode r virtualvoiddelBinTree TBinTreeNode r templatestructTBinTreeNode TBinTreeNode lchild rchild TElemdata 二叉树初始化和终止 templateTBinTree TBinTree root NULL numNodes 0 templateTBinTree TBinTree if root cout nDeltethisBiTreeindesConstructfunction n delBinTree root 创建二叉树 templatevoidTBinTree preCreateBinTree TBinTreeNode r TElemch cin ch if ch r NULL else if r TBinTreeNode malloc sizeof TBinTree exit 1 if root NULL root r numNodes r data ch preCreateBinTree 二叉树前序遍历 templatevoidTBinTree preTraverse TBinTreeNode r if r coutdatalchild preTraverse r rchild 二叉树中序遍历 templatevoidTBinTree inTraverse TBinTreeNode r if r inTraverse r lchild coutdatarchild 二叉树后序遍历 templatevoidTBinTree postTraverse TBinTreeNode r if r postTraverse r lchild postTraverse r rchild coutdata 递归算法的跟踪 以如下二叉树为例 用T x 表示遍历算法 它表示遍历以x为根的子树 用P x 表示输出 访问结点x 方框中左边括号中的数字表示子程序调用序号 图6一棵二叉数 二叉树的前序遍历递归算法执行过程 二叉树前序遍历 堆栈实现 templatevoidTBinTree preTraverse stack TBinTreeNode r TStackSqu preStack 50 TBinTreeNode ptr ptr r if ptr NULL return coutdatalchild coutlchild datalchild ptr ptr lchild else ptr preStack Pop if ptr rchild coutrchild datarchild ptr ptr rchild while preStack IsEmpty 二叉树层序遍历 templatevoidTBinTree levelTraverse TBinTreeNode r TQueueLink levelQ TBinTreeNode ptr if r levelQ QPush r while levelQ IsEmpty ptr TBinTreeNode levelQ QPop coutdatalchild levelQ QPush ptr lchild if ptr rchild levelQ QPush ptr rchild 删除二叉树 templatevoidTBinTree delBinTree TBinTreeNode r if r delBinTree r lchild delBinTree r rchild deleter 二叉树遍历的应用 统计二叉树叶子结点的个数 先序遍历 templatevoidTBinTree countLeaf TBinTreeNode r int 二叉树遍历的应用 templateintTBinTree depthBitree TBinTreeNode r intdepthval depthLeft depthRight if r depthval 0 else depthLeft depthBitree r lchild depthRight depthBitree r rchild depthval 1 depthLeft depthRight depthLeft depthRight returndepthval 求二叉树的深度 后序遍历 6 8树与森林 前面已给出树与森林的概念 但只是重点介绍了二叉树 本节开始讨论树与森林操作 存储及其与二叉树的转化等问题 树的存储结构 树的存储有多种方式 既可以采用顺序存储结构 也可以采用链式存储结构 但无论采用何种存储方式 都要求存储结构不但能存储各结点本身的数据信息 还要能唯一地反映树中各结点之间的逻辑关系 双亲表示法孩子链表表示法孩子兄弟表示法 树的示例图 双亲表示法 defineMAXNODEtemplatestructTTreeNodeP TElemdata intparent structTTreeNodePt MAXNODE 序号dataparent 邻接表法 defineMAXNODE 链结点定义templatestructTTreeLinkNode longchildNodeId structTTreeLinkNode nextchild 树结点定义templatestructTTreeNodeAdj TElemdata structTTreeLinkNode firstchild longfatherId longnumsons structTTreeNodeAdjt MAXNODE 序号dataparent 1 5 4 8 7 6 3 2 孩子兄弟表示法 templatestructTreeNodeBinLink TElemdata structTreeNodeBinLink firstson structTreeNodeBinLink nextBrother 树 森林与二叉树之间的转化 与树相比 二叉树的存储与操作实现要简单一些 若能将树确定地转化为二叉树 并可确定地将转化后的结果还原为原树 则对树的处理就转化为对二叉树的处理了 树转换为二叉树的方法 将一棵树转换为二叉树的方法是 1 树中所有相邻兄弟之间加一条连线 2 对树中的每个结点 只保留它与第一个孩子结点之间的连线 删去它与其它孩子结点之间的连线 3 以树的根结点为轴心 将整棵树顺时针转动一定的角度 使之结构层次分明 树转换为二叉树示例 森林转化为二叉树的方法 1 若F为空 即m 0 则B为空树 2 若F非空 即m 0 则B的根root即为森林中第一棵树的根Root T1 B的左子树LB是从T1中根结点的子树森林F1 T11 T12 T1m1 转换而成的二叉树 其右子树RB是从森林F T2 T3 Tm 转换而成的二叉树 森林转化为二叉树示例 树与森林的遍历 一 树的遍历由于树不象二叉树那样 根位于二棵子树的中间 故一般无 中序 一说 树一般只有先根和后根及层序三种遍历方法 关于层序遍历 与二叉树相同 1 先根遍历先根遍历以root为根的树 子树 的规则为 若root为空 则无动作 结束 若root不空 则先访问根结点 然后按此规则 先根 按各子树的次序 若为无序树 则次序任意 分别遍历root的各子树 2 后根遍历后根遍历以root为根的树 子树 的规则为 若root为空 则无动作 结束 若root不空 则按后根遍历规则 按各子树的次序 若为无序树 则次序任意 分别遍历root的各子树 然后访问根 例6 6对图所示树的遍历结果为 先根 ABEFCDG后根 EFBCGDA 树的先根遍历与其转换的相应二叉树的先序遍历的结果序列相同 树的后根遍历与其转换的相应二叉树的中序遍历的结果序列相同 因此树的遍历算法是可以采用相应二叉树的遍历算法来实现的 二 森林的遍历森林可有三种遍历方式 前序遍历 后序遍历及层序遍历 层序遍历与二叉树相同 1 前序遍历若森林为空 则无动作 返回 若森林非空 则 先访问森林中的第1棵子树的根结点 前序遍历第1棵子树的根的各子树构成的森林 前序遍历除去第1棵子树后剩余子树构成的森林 2 后序遍历 中序遍历若森林为空 则无动作 返回 若森林不空 则 后序遍历森林中第1棵子树的根结点的各子树构成的森林 访问第1棵子树的根 后序遍历除去第1棵子树后剩余子树构成的森林 例6 7对图所示森林的遍历结果为 前序 ABCDEFGHJIK后 中序 BADEFCJHKIG 森林的前序遍历和中序遍历与所转换的二叉树的先序遍历和中序遍历的结果序列相同 6 10树的应用示例 哈夫曼树 最优树的定义如何构造最优树前缀编码 最优树的定义 结点的路径长度 从根结点到该结点的路径上分支的数目树的路径长度 树中每个结点的路径长度之和 树的带权路径长度 树中所有叶子结点的带权路径长度之和 其中Wi为第i个叶结点的权值 Pi为第i个叶结点的路径长度 在所有含n个叶子结点 并带相同权值的m叉树中 必存在一棵带权路径长度最小的树 其被称为 最优树 带权路径长度示例 a b c 这三棵树的带权路径长度分别为 a WPL 1 2 3 2 5 2 7 2 32 b WPL 1 3 3 3 5 2 7 1 29 c WPL 7 3 5 3 3 2 1 1 43 要使二叉树的WPL值最小 必须使权值越大的叶结点越靠近根结点 而权值越小的叶结点越远离根结点 哈夫曼树 最优树 构造算法 我们假定已知n个权值W w1 w2 wn 构造一棵具有n个叶子且叶子权分别对应这n个值的哈夫曼树 具体步骤如下 1 初试化 构造一个森林F w1 w2 wn 它有n棵树 每棵树只有一个结点 且其权分别为给定的n个权值 2 找最小树 从F中找两棵根权最小的树 分别以它们为左右子树 构造一棵新树 并令新树的根的权为这两棵根权之和 3 删除 从F中将所找到的两棵最小树删除4 加入 将新构造的树加入F 5 判断 若F中只剩一棵树 则结束 其即为所求 否则 转2 例6 8设W 2 3 5 6 7 则构造对应的哈夫曼树的过程如图所示 哈夫曼树构造算法的实现 数据结构的存储考虑哈夫曼树是一种二叉树 其当然可采用前面给出的存储方法 这里采用一维数组存储哈夫曼树的方法 各结点存储在一维数组中 0号位置不使用 从1号位置起存储 设哈夫曼树有n个叶子 则由前面的定理知 其结点总数为2n 1 每个结点的结构为 权值 父亲序号 左儿子序号 右儿序号 叶子集中存储在前面部分 即1 n的位置 而 n 1 2n 1 存储其余结点 用0表示空指针 程序实现 哈夫曼编码基本概念 在数据通讯中 经常需要将传送的文字转换成由二进制字符0 1组成的二进制串 我们称之为编码 传送电文时 我们总是希望传送时间尽可能短 这就要求电文代码尽可能短 等长编码 每个字符采用相同位数的编码方式 不等长编码 如果在编码时考虑字符出现的频率 让出现频率高的字符采用尽可能短的编码 出现频率低的字符采用稍长的编码 构