数据结构7树形结构.ppt

第七章树形结构 在前面几章中介绍了各种常用的线性结构 本章介绍非线性结构 其中树型结构就是一种典型的非线性结构 线性结构可以表示元素或结点的相邻关系 而在树型结构中 由于一个结点与多个结点相对应 所以树型结构除用于表示相邻关系外 还可以表示层次关系 树型结构是一类重要的非线性数据结构 其中又以树和二叉树最为常用 直观角度看 树是以分支关系定义的层次结构 树在计算机领域中得到广泛应用 如文件管理中的目录结构 数据库系统中的信息组织形式等 树结构在客观世界中也广泛存在 如人类社会的族谱和各种社会组织机构等都可用树来形象表示 树应用举例 a b c d e f 本章重点讨论二叉树的存储结构及各种操作 并研究树和森林与二叉树之间的转换关系 7 1树的定义和基本术语 7 1 1树的定义 一 非数学语言定义树 Tree 是n n 0 n 0为空树 个结点的有限集合 在任意一棵非空树中 1 当n 0时有且仅有一个特定的称为根 Root 的结点 2 其余结点可分为m个 m 0 互不相交的有限集T1 T2 Tm其中每一个集合Ti本身又是一棵树 并且称为根的子树 SubTree 例7 1 只有根结点的树 A 例7 2 一般的树 该树T由子树T1和T2和组成 T1包括 例7 3 不是一棵树 因为 子树Tree H H M 子树Tree I I M 出现了交叉 违反树的定义 树的定义是递归的 因为在树的定义中有用到树的定义 它刻画了树的固有特性 即一棵树由若干棵子树构成 而子树又由更小的若干棵子树构成 树是一种非线性数据结构 具有以下特点 它的每个节点都可以有不止一个后继 除根以外的所有结点 都有且只有一个前驱 这些数据结点按分支关系组织起来 清晰地反映了数据元素之间的层次关系 可以看出 数据元素之间存在的关系是一对多的 或者多对一的关系 补充说明树的分类 1 自由树 无根树 结点的排列无关紧要 2 有根树 根结点位于树的顶 默认讨论的树 3 有序树 能表示第一个孩子 第二孩子 如族谱 二叉树就是有序的 二 树的形式化定义 数学语言定义 树定义为集合 T K R K是包含n个结点的有穷集合 n 0 关系R满足以下条件 1 有且仅有一个结点k0 K 它对于关系R来说没有前驱结点 结点k0称作树的根 2 除结点k0外 K中的每个结点对于关系R来说都有且仅有一个前驱结点 3 K中每个结点对于关系R来说可以有多个后继结点 三 抽象数据类型树的定义 ADTTree 数据对象 D ai 1 i n n 0 ai ElemType类型 数据关系 R ai aj D 1 i n 1 j n 其中每个元素只有一个前驱 可以有零个或多个后继结点 有且仅有一个元素没有前驱 基本运算 InitTree 求元素t的后继 7 1 2树的逻辑表示方法 其它表示形式 1 树形表示法 这是树的最基本的表示 使用一棵倒置的树表示树结构 非常直观和形象 2 集合法Tree A的结构 结点A包括 B C D 结点B包括 E F 结点C包括 G 结点D包括 H I J 结点E包括 K L 结点H包括 M 3 范式图法或文氏图法 VennDiagram 每棵树对应一个圆圈 圆圈包含根结点和子树的圆圈 同一棵根结点下的各子树对应的圆圈是不能相交的 A B C D E F G H I J K L M A B C D B E F C G D H I J E K L H M 4 缩格法 Indentation 或凹入表示法 A B C D E F G H I J K L M 5 嵌套括弧法 NestedParentheses 用最外层括弧表示树的根 子树嵌套在根括弧之内 A B C D E F G H I J K L M 6 层数号码法 LevelNumberFormat 用层数来表示结点所在的位置1 A 2 B2 C2 D 3 E3 F3 G3 H3 I3 J 4 K4 L4 M A B C D B E F C G D H I J E K L H M 7 1 3树的基本术语 结点的度和树的度 1 结点拥有的子树的个数称为该结点的度 结点A的度为3 B的度为2 C的度为1 D的度为3 F G I J K L和M的度为0 2 树中各结点度的最大值称为树的度 通常将度为m的树称为m次树 如左图树A的度为3 分支结点与叶结点 1 度不为0的结点称为非终端结点 又叫分支结点 2 度为0的结点称为终端结点或叶结点 3 在分支结点中 每个结点的分支数就是该结点的度 如对于度为1的结点 其分支数为1 被称为单分支结点 对于度为2的结点 其分支数为2 被称为双分支结点 其余类推 路径与路径长度 对于任意两个结点ki和kj 若树中存在一个结点序列ki ki1 ki2 kin kj 使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继 则称该结点序列为由ki到kj的一条路径 用路径所通过的结点序列 ki ki1 ki2 kj 表示这条路径 路径的长度等于路径所通过的结点数目减1 即路径上分支数目 可见 路径就是从ki出发 自上而下 到达kj所通过的树中结点序列 显然 从树的根结点到树中其余结点均存在一条路径 例如 A到L的路径 A ki B ki1 E ki2 L kj 也可以表示为 A B E J 路径长度 3 有以下两种计算方法 结点数 1 分支数 孩子结点 双亲结点和兄弟结点 在一棵树中 每个结点的后继 被称作该结点的孩子结点 或子女结点 相应地 该结点被称作孩子结点的双亲结点 或父母结点 具有同一双亲的孩子结点互为兄弟结点 进一步推广这些关系 可以把每个结点的所有子树中的结点称为该结点的子孙结点 从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点 结点的层次和树的高度树中的每个结点都处在一定的层次上 结点的层次从树根开始定义 根结点为第1层 它的孩子结点为第2层 以此类推 一个结点所在的层次为其双亲结点所在的层次加1 树中结点的最大层次称为树的高度 或树的深度 有序树和无序树 若树中各结点的子树是按照一定的次序从左向右安排的 且相对次序是不能随意变换的 则称为有序树 否则称为无序树 如家族的族谱就是有序树 可以表示子女之间的大小关系 森林 n n 0 个互不相交的树的集合称为森林 森林的概念与树的概念十分相近 因为只要把树的根结点删去就成了森林 反之 只要给n棵独立的树加上一个结点 并把这n棵树作为该结点的子树 则森林就变成了树 7 1 4树的性质性质1 树中的结点数等于所有结点的度数加1 证明 根据树的定义 在一棵树中除树根结点外 每个结点有且仅有一个前驱结点 也就是说 每个结点与指向它的一个分支一一对应 所以除树根之外的结点数等于所有结点的分支数 度数 从而可得树中的结点数等于所有结点的度数加1 除树根结点外 每个结点与指向它的一个分支一一对应 1 2 3 4 5 6 7 8 9 10 11 12 除树根之外的结点数等于分支数 结点度数和 性质2 度为m的树中第i层上至多有mi 1个结点 i 1 证明 采用数学归纳法 对于第一层 因为树中的第一层上只有一个结点 即整个树的根结点 而由i 1代入mi 1 得mi 1 m1 1 1 也同样得到只有一个结点 显然结论成立 假设对于第 i 1 层 i 1 命题成立 即度为m的树中第 i 1 层上至多有mi 2个结点 则根据树的度的定义 度为m的树中每个结点至多有m个孩子结点 所以第i层上的结点数至多为第 i 1 层上结点数的m倍 即至多为mi 2 m mi 1个 这与命题相同 故命题成立 性质3 高度为h的m次树至多有个结点 证明 由树的性质2可知 第i层上最多结点数为mi 1 i 1 2 h 显然当高度为h的m次树 即度为m的树 上每一层都达到最多结点数时 整个m次树具有最多结点数 因此有 整个树的最多结点数 每一层最多结点数之和 m0 m1 m2 mh 1 当一棵m次树上的结点数达到 mh 1 m 1 则称该树为满m次数 例如高度为3的满2次树 每个结点的度最大为2 总结点数 23 1 2 1 7 性质4 具有n个结点的m次树的最小高度为 logm n m 1 1 证明 略 例7 4 若一棵三次树中度为3的结点个数为2 度为2的结点个数为1 度为1的结点个数为2 则该三次树中总的结点个数和度为0的结点个数分别是多少 解 设该三次树中总的结点个数 n度为0的结点个数 n0度为1的结点个数 n1度为2的结点个数 n2度为3的结点个数 n3 由已知条件得到 n1 2 n2 1 n3 2由树的性质1可知 树中的结点数等于所有结点的度数加1 n 0 n0 1 n1 2 n2 3 n3 1 11又因为 n n0 n1 n2 n3即 n0 n n1 n2 n3 11 2 1 2 6所以该三次树中总的结点个数和度为0的结点个数分别是11和6 7 1 5树的基本运算由于树是非线性结构 结点之间的关系较线性结构复杂得多 所以树的运算较以前讨论过的各种线性数据结构的运算要复杂许多 树的运算主要分为三大类 1 第一类 寻找满足某种特定关系的结点 如寻找当前结点的双亲结点等 2 第二类 插入或删除某个结点 如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等 3 第三类 遍历树中每个结点 重点内容 树的遍历运算是指按某种方式访问树中的每一个结点 且每一个结点只被访问一次 树的遍历运算的算法主要有先根遍历和后根遍历两种 注意 下面的先根遍历和后根遍历算法都是递归的 1 先根遍历先根遍历过程为 1 访问根结点 2 按照从左到右的次序先根遍历根结点的每一棵子树 例7 5 求该树的先序遍历次序 1 访问根结点 2 按照从左到右的次序先根遍历根结点的每一棵子树 R 按照从左到右的次序先根遍历子树A B C遍历每个子树时又要按照原则 1 和 2 进行即遍历B之前应完成A的遍历 A D E B C F G H K 2 后根遍历后根遍历过程为 1 按照从左到右的次序后根遍历根结点的每一棵子树 2 访问根结点 遇到R时不访问 要待到其所有子树全部访问完毕 左至右 即准备访问A 处理A时遵守同样的规则 D E A B G H K F C R 练习 写出下面这棵树的先根和后根遍历次序 先根遍历 A B E K L F C G D H M I J后根遍历 K L E F B G C M H I J D A 7 1 6树的存储结构树的存储既要求保存结点的数据元素本身 又要存储结点之间的逻辑关系 1 二维数组表示法 ArrayRepresentation 补充 数组中的行数目用树中结点数的数目表示 列数用树的度 1表示 例7 6 该树有13个结点即数组有13行 树的度为3所以数组要有4列 12345678910111213 1234ABCDEFGHIJKLM 123 子树根的地址 45 6 7891011 12 特点 查找任一结点的孩子结点非常方便 查找父结点麻烦解决方法 增加一列存储父结点的地址 5 1000112333447 2 双亲存储结构这种存储结构是一种顺序存储结构 用一组连续空间存储树的所有结点 同时在每个结点中附设一个伪指针 下标 指示其双亲结点的位置 按层及由左到右的顺序给结点编号 0 1 2 3 4 5 6 7 8 9 用一维数组来存储这10个结点每个结点对应一个数组元素每个元素包括两个域 数据域 存放该结点所包含的数据指针域 指出该结点的双亲结点的位置 0R 1 1A 0 2B0 3C0 4D1 5E1 6F3 7G6 8H6 9K6 特点 利用每个结点只有一个双亲 除根以外 的特性 求某个结点的双亲结点十分容易 但求某个结点的孩子结点时需要遍历整个结构 结点描述 defineMAX TREE SIZE100typedefstructPTNode TElemTypedata intparent PTNode typedefstruct PTNodenodes MAX TREE SIZE intn 结点的个数 Ptree 存储结构的讨论 现有另一棵树 10W 111X1012Y1013Z10 多棵树可共享存储空间 适用查找父结点 不适用查找孩子结点 面向对象技术中等价类的应用与该存储摸式的思路一致 如果树合并 0 1 3 孩子链表存储结构 1 基本存储方式 每个结点所含域的个数由各结点的度来决定 Head B 用数组表示树时操作方式简单 但浪费内存 以链表表示树节省空间 但每个结点的结构不同 因此进行插入和删除操作时的流程非常复杂 改进的方法是使每个节点结构相同 域的个数即为树的度数 2 改进一 各结点的结构一致 指针域的个数即为树的度数 该树的度为3 Head 此方法的空间利用率并不高 树的存储结构有很多 都有各自的优缺点 常用的方式将顺序与链式的特性结合在一起 3 改进二 整体是一个数组 一个元素存一个结点每个结点有两个域 数据域 指针域 链表头 每个结点指针指向自己的第一个孩子 每个孩子指针按顺序指向自己第一个兄弟 data link 0R1A2B3C4D5E6F7G8H9K 下标序号 存储方式类似双亲存储结构 区别在于指针域不是下标 表示R的第一个孩子存储在1号下标元素中 第二个在2号 第三个在3号 访问时只要找到第一个孩子就可以沿孩子链表寻访所有子树 表示父子关系 表示兄弟关系 结构描述 defineMAX TREE SIZE100typedefstructCTNode intchild structCTNode next ChildPtr typedefstruct TElemTypedata ChildPtrfirstchild 孩子链表头指针 CTBox typedefstruct CTBoxnodes MAX TREE SIZE Ctree 孩子结点结构 数据元素的结构 讨论 插入结点 如插入X为A的孩子 增加数组元素并修改链表 删除结点要引起数据移动该结构在图中还将用到 4 改进三 带双亲的孩子链表 结点由三个域组成 数据域 指向第一个孩子的指针域和指向双亲的指针域即在孩子表示法中增加一个指向双亲的指针域 引入双亲存储结构的理念 即可以访问每个结点的孩子 也可访问双亲 4 孩子 兄弟链存储结构孩子兄弟链存储结构是为每个结点设计三个域 一是数据元素域 二是该结点第一个孩子结点的指针域 三是该结点下一个兄弟结点的指针域 Head 结点描述 typedefstructtnode ElemTypedata structtnode hp 指向兄弟 structtnode vp 指向孩子结点 tnode 7 1 7树的