[理学]数据结构7树形结构.ppt

第七章 树形结构 在前面几章中介绍了各种常用的线性结构，本章介绍非线性结构，其中树型 结构就是一种典型的非线性结构。线性结构可以表示元素或结点的相邻关系，而 在树型结构中，由于一个结点与多个结点相对应，所以树型结构除用于表示相邻 关系外，还可以表示层次关系。 树型结构是一类重要的非线性数据结构，其中又以树和二叉树最为常用。直 观角度看，树是以分支关系定义的层次结构。树在计算机领域中得到广泛应用， 如文件管理中的目录结构、数据库系统中的信息组织形式等。树结构在客观世界 中也广泛存在，如人类社会的族谱和各种社会组织机构等都可用树来形象表示。 树应用举例 书名 第一章第二章 第章 第1节 + * ab -f c/ de a*b+(c-d/e)*f 本章重点讨论二叉树的存储结构及各种操作,并研究树和森林 与二叉树之间的转换关系。 7.1 树的定义和基本术语 7.1.1 树的定义： 一、非数学语言定义 树(Tree)是n(n0，n=0为空树)个结点的有限集合。在任意一棵非空树中： 1. 当 n 0 时有且仅有一个特定的称为根(Root)的结点； 2. 其余结点可分为 m 个(m0)互不相交的有限集T1,T2,Tm 其中每一个集合 Ti 本身又是一棵树，并且称为根的子树(SubTree)。 例7.1：只有根结点的树 A 例7.2：一般的树 A B E C DFG HI 树T 该树T由子树T1和T2和组成 B EDF HI T1 C G T2 T1包括： D T11 E HI T12 F T13 H T121 I T122 G T21 例7.3： A BCD EFGHIJ KLM 不是一棵树, 因为: 子树 Tree-H=H，M子树 Tree-I=I，M 出现了交叉，违反树的定义。 树的定义是递归的，因为在树的定义中有用到树的定义。它刻画了树的固有 特性，即一棵树由若干棵子树构成，而子树又由更小的若干棵子树构成。 树是一种非线性数据结构，具有以下特点： 它的每个节点都可以有不止一个后继(除根以外的所有结点)，都有且只有一个 前驱； 这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。 可以看出，数据元素之间存在的关系是一对多的，或者多对一的关系。 补充说明树的分类： (1) 自由树(无根树)：结点的排列无关紧要。 结点 数为1 结点 数为2 结点 数为3 结点 数为4 (2) 有根树：根结点位于树的顶。(默认讨论的树) 结点 数为1 结点 数为2 结点 数为3 结点 数为4 (3) 有序树：能表示第一个孩子、第二孩子(如族谱、二叉树就是有序的) 二、树的形式化定义：(数学语言定义) 树定义为集合：TK,R。K是包含 n 个结点的有穷集合(n0)，关系R满 足以下条件： (1) 有且仅有一个结点k0K，它对于关系 R 来说没有前驱结点，结点k0称 作树的根。 (2) 除结点k0外，K中的每个结点对于关系R来说都有且仅有一个前驱结点。 (3) K中每个结点对于关系R来说可以有多个后继结点。 三、抽象数据类型树的定义： ADT Tree 数据对象： D=ai|1in,n0，aiElemType类型 数据关系： R=|ai,ajD,1in,1jn,其中每个元素只有一个前驱， 可以有零个或多个后继结点，有且仅有一个元素没有前驱 基本运算： InitTree( /*初始化树：构造一个只有一个元素的树*/ ClearTree(/*销毁树：释放树t占用的存储空间*/ Parent(t);/*求元素t的前驱*/ Sons(t); /*求元素t的后继*/ 7.1.2 树的逻辑表示方法(其它表示形式) 1. 树形表示法：这是树的最基本的表示，使用一棵倒置的树表示树结构，非常 直观和形象。 A BCD EFGHIJ KLM 2. 集合法 Tree-A的结构： 结点A包括B,C,D 结点B包括E,F 结点C包括G 结点D包括H,I,J 结点E包括K,L 结点H包括M A BCD EFGHIJ KLM 3. 范式图法或文氏图法(Venn Diagram) 每棵树对应一个圆圈，圆圈包含根结点和子树的圆圈，同一棵根结点下的各 子树对应的圆圈是不能相交的。 A B C D E F G H I J KL 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. 嵌套括弧法(Nested Parentheses) 用最外层括弧表示树的根，子树嵌套在根 括弧之内。 (A(B ,C ,D )(E ,F)(G)(H ,I,J)(K,L)(M) 6. 层数号码法(Level Number Format) 用层数来表示结点所在的位置 1 A 2 B 2 C 2 D 3 E 3 F 3 G 3 H 3 I 3 J 4 K 4 L 4 M A:B,C,D B:E,F C:G D:H,I,J E:K,L H:M 7.1.3 树的基本术语 结点的度和树的度： (1) 结点拥有的子树的个数称为该结点的度； A BCD EFGHIJ KLM 结点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 BCD EFGHIJ KLM 例如：A 到 L 的路径： A(ki)B(ki1)E(ki2)L(kj) 也可以表示为： (A,B,E,J) 路径长度：3，有以下两种计算方法 - 结点数 1 - 分支数 孩子结点、双亲结点和兄弟结点： 在一棵树中，每个结点的后继，被称作该结点的孩子结点(或子女结点)。相 应地，该结点被称作孩子结点的双亲结点(或父母结点)。具有同一双亲的孩子结 点互为兄弟结点。进一步推广这些关系，可以把每个结点的所有子树中的结点称 为该结点的子孙结点，从树根结点到达该结点的路径上经过的所有结点被称作该 结点的祖先结点。 结点的层次和树的高度 树中的每个结点都处在一定的层次上。结点的层次从树根开始定义，根结点 为第1层，它的孩子结点为第2层，以此类推。一个结点所在的层次为其双亲结点 所在的层次加1。树中结点的最大层次称为树的高度(或树的深度)。 有序树和无序树： 若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能 随意变换的，则称为有序树，否则称为无序树。 如家族的族谱就是有序树，可以表示子女之间的大小关系。 森林： n (n0) 个互不相交的树的集合称为森林。森林的概念与树的概念十分相 近，因为只要把树的根结点删去就成了森林。反之，只要给 n 棵独立的树加上 一个结点，并把这 n 棵树作为该结点的子树，则森林就变成了树。 7.1.4 树的性质 性质1：树中的结点数等于所有结点的度数加1。 证明： 根据树的定义，在一棵树中除树根结点外，每个结点有且仅有一个前驱结点。 也就是说，每个结点与指向它的一个分支一一对应，所以除树根之外的结点数等 于所有结点的分支数(度数)，从而可得树中的结点数等于所有结点的度数加1。 A BCD EFGHIJ KLM 除树根结点外，每个结点与指向它的一个分支 一一对应;1 23 456 789 101112 除树根之外的结点数等于分支数(结点度数和); 性质2：度为 m 的树中第 i 层上至多有 mi-1个 结点，i1。 证明：(采用数学归纳法) 对于第一层，因为树中的第一层上只有一个结点，即整个树的根结点，而由 i=1 代入mi-1，得 mi-1=m1-1=1，也同样得到只有一个结点，显然结论成立。 假设对于第(i-1)层(i1)命题成立，即度为 m 的树中第(i-1)层上至多有 mi-2个结点。 则根据树的度的定义，度为m的树中每个结点至多有 m 个孩子结点，所以第 i 层上的结点数至多为第(i-1)层上结点数的 m 倍，即至多为mi-2m=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 1 23 4567 性质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 = 0n0 + 1n1 + 2n2 + 3n3 + 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 ABC DEF G HK 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 BCD EFGHIJ KLM 练习：写出下面这棵树的先根和后根遍历次序。 先根遍历：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. 二维数组表示法(Array Representation,补充) 数组中的行数目用树中结点数的数目表示，列数用树的度+1表示。 例7.6： A BCD EFGHIJ KLM A:B,C,D B:E,F C:G D:H,I,J E:K,L H:M 该树有13个结点即数组有13行，树的度为3所以数组要有4列 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 A B C D E F G H I J K L M 1 2 3 (子树根的地址) 4 5 - 6 - - 7 8 9 10 11 - - - - - - - 12 - - - - - - - - - - - - - - - - - 特点：查找任一结点的孩子结点非常方 便，查找父结点麻烦 解决方法：增加一列存储父结点的地址 5 -1 0 0 0 1 1 2 3 3 3 4 4 7 2. 双亲存储结构 这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有结点，同 时在每个结点中附设一个伪指针(下标)指示其双亲结点的位置。 R ABC DEF G HK 按层及由左到右的顺序给结点编号： 0 1 2 3 45 6 789 用一维数组来存储这10个结点 每个结点对应一个数组元素 每个元素包括两个域 数据域: 存放该结点所包含的数据 指针域: 指出该结点的双亲结点的位置 数组 下标 结点的 数据域 双亲 位置 0 R-1 1 A0 2 B 0 3 C 0 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 K 6 特点: 利用每个结点只有一个双亲(除根以外)的特性； 求某个结点的双亲结点十分容易，但求某个结点的孩子结点 时需要遍历整个结构。 结点描述： #define MAX-TREE-SIZE 100 typedef struct PTNode TElemType data; int parent; PTNode; typedef struct PTNode nodesMAX-TREE-SIZE; int n; /*结点的个数*/ Ptree; R ABC DEF G HK 0 1 2 3 45 6 789 数组 下标 结点的 数据域 双亲 位置 0 R-1 1 A0 2 B 0 3 C 0 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 K 6 存储结构的讨论： 现有另一棵树： W XY Z 10 W -1 11 X 10 12 Y 10 13 Z 10 - 多棵树可共享存储空间 - 适用查找父结点，不适用查找孩子结点 - 面向对象技术中等价类的应用与该存储摸式的思路一致 如果树合并： 0 1 R ABC DEF G HK 3. 孩子链表存储结构 (1) 基本存储方式 每个结点所含域的个数由各结点的度来决定。 Head R ABC DEF GHK 用数组表示树时操作方式简单，但浪费内 存；以链表表示树节省空间，但每个结点 的结构不同，因此进行插入和删除操作时 的流程非常复杂。 改进的方法是使每个节点结构相同。 域的个数即为树的度数。 R ABC DEF G HK (2) 改进一：各结点的结构一致(指针域的个数即为树的度数，该树的度为3) Head R A B C D E F GHK 此方法的空间利用率并不高； 树的存储结构有很多，都有各自的优缺点。常用的方式将 顺序与链式的特性结合在一起。 (3) 改进二:整体是一个数组、一个元素存一个结点 每个结点有两个域：数据域、指针域(链表头)； 每个结点指针指向自己的第一个孩子； 每个孩子指针按顺序指向自己第一个兄弟； R ABC DEF G HK datalink 0 R 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 K 下标序号12 3 存储方式类似双亲存储结构(区别在于指针域不是下标) 表示R的第一个孩子存储在1 号下标元素中、第二个在2 号、第三个在3号。访问时 只要找到第一个孩子就可以 沿孩子链表寻访所有子树。 45 6 789 表示父子关系 表示兄弟关系 datalink 0 R 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 K 表头指针12 3 45 6 789 结构描述： #define MAX-TREE-SIZE 100 typedef struct CTNode int child; struct CTNode *next; *ChildPtr; typedef struct TElemType data; ChildPtr firstchild;/*孩子链表头指针*/ CTBox; typedef struct CTBox nodesMAX-TREE-SIZE; Ctree; 孩子结点结构 数据元素的结构 讨论： 插入结点(如插入X为A的孩子) R ABC DEF G HK X - 增加数组元素并修改链表 X10 10 删除结点要引起数据移动 该结构在图中还将用到 (4) 改进三：带双亲的孩子链表 结点由三个域组成: 数据域、指向第一个孩子的指针域 和指向双亲的指针域 即在孩子表示法中增加一个指向双亲的指针域(引入双 亲存储结构的理念) R ABC DEF G HK 0 1 2 3 45 6 789 datalink 0 R 1 A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 K 123 45 6 789 parent 0 -1 1 0 2 0 3 0 4 1 5 1 6 3 7 6 8 6 9 6 即可以访问每个结点的孩子，也可访问双亲。 4. 孩子、兄弟链存储结构 孩子兄弟链存储结构是为每个结点设计三个域：一是数据元素域、二是该结 点第一个孩子结点的指针域、三是该结点下一个兄弟结点的指针域。 R ABC DEF G HK Head R A D B C F E G HK 结点描述： typedef struct tnode ElemType data; struct tnode *hp;/*指向兄弟*/ struct tnode *vp;/*指向孩子结点*/ tnode 7.1.7 树的应用(补充) 例7.7 皇后问题: 皇后(N-Queens)问题是将N个棋子摆入一个NN的矩阵，并且规定每一行、每 一列、每一从右上到左下、从左上到右下的斜线，均只放置一个棋子，不能有重 复的情形发生。以44为例： 矩阵中放入棋子时以数码编号， 1