东南大学数据结构_Lec005

1、引言 树型结构是一类非常重要的非线性结构。 树型结构是以分支关系定义的层次结构。 树在计算机领域中也有着广泛的应用：在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法行为时，可用树来描述其执行过程等。数据结构1第5讲 树和二叉树树的存储结构初识二叉树2数据结构树的定义 树(Tree)是 n (n0) 个结点的有限集。n=0 时称为空树。 在任意一棵非空树中： 有且仅有一个特定的称为根 (Root) 的结点； 当 n1 时，其余结点可分为 m (m0) 个互不相交的有限集 T1, T2, , Tm，其中每一个集合本身又是一棵树，并且称为根的子树 (Subtre

2、e)。树的定义用到树的概念 递归定义数据结构3ADHIJBEFKLCGMNA(a) 只有根结点(b) 一般的树BEFKLCGMNDHIJ树的结点分类树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶子 (Leaf) 或终端结点。度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。 数据结构4ABCE根结点内部结点分支结点或非终端结点叶结点或终端结点FDGHIJ此结点度为此结点度为1 1此结点度为此结点度为2 2此结点度为此结点度为0 0树的结点间关系结点的子树的根称为该结点的

3、孩子(Child)，相应地，该结点称为孩子的双亲 (Parent)；同一个双亲的孩子之间互称兄弟(Sibling)；结点的祖先是从根到该结点所经分支上的所有结点；以某结点为根的子树中的任一结点都称为该结点的子孙。数据结构5ABCEFDGHIJC,我们是兄弟我们是兄弟A,我是你的孩子我是你的孩子D,我是你双亲我是你双亲树的层次结点的层次 (Level) 从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在第l+1层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。数据结构6ABCEFDGHIJ第一层第一层第二层第二层第三层第三层第四

4、层第四层深度为深度为4堂兄弟堂兄弟有序树、无序树与森林如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。森林(Forest) 是 m (m0) 棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林；在逻辑结构上，任何一棵树是一个二元组二元组 Tree = (root, F) 其中：root是数据元素，称作树的根节点； F是 m 棵树的森林，F = (T1, T2, , Tm) ； Ti = (ri, Fi ) 称做根 root 的第 i 棵子树。当 m0 时，树根和其子树森林之间存在下列关系： RF = | i = 1, 2, , m, m0

5、 用于森林和树与二叉树之间转换的递归定义。数据结构7树的其他表示形式a)嵌套集合：一些集合的集体，对于任何两个集合，或者不相交，或者一个包含另一个；b)广义表形式：根作为由子树森林组成的表的名字写在表的左边；c)凹入表示法：类似书的编目。数据结构8a)嵌套集合HIJDFBKLECMNGAb) 广义表形式(A(B(E(K, L), F), C(G(M, N), D(H, I, J)c) 凹入表示法ABEKLFGHIJCDMN线性结构 VS 树结构 线性结构 第一个数据元素：无前驱无前驱 最后一个数据元素：无后继无后继 中间元素：一个前驱一个后继一个前驱一个后继数据结构9 树结构 根结点：无双亲，

6、唯一无双亲，唯一 叶结点：无孩子，可以多个无孩子，可以多个 中间结点：一个双亲多个孩子一个双亲多个孩子树的抽象数据类型定义ADT Tree数据对象D：D是具有相同数据类型的数据元素的集合。数据关系R：若D为空集，则称为空树； 若D仅含一个数据元素，R为空集； 基本操作P： 构造树、销毁树； 返回树的深度、树的根、树中某结点的值，； 插入子树、删除子树； 遍历树； ADT Tree数据结构10第5讲 树和二叉树树的基本概念初识二叉树11数据结构树的存储结构 顺序存储结构：用一段地址连续的存储单元依次存储线性表数据元素。 对于一对多的树结构呢？ 充分利用顺序存储和链式存储结构的特点实现树的存储结构

7、的表示。双亲表示法（顺序存储）孩子表示法（链式存储）孩子兄弟表示法数据结构12双亲表示法假设以一组连续存储空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在数组中的位置（数组下标值）。数组元素及数组的类型定义：#define MAX_SIZE 100typedef struct PTNode ElemType data ; int parent ;PTNode ; 数据结构13typedef struct PTNode NodesMAX_SIZE ;int root; /* 根结点位置 */int num ; /* 结点数 */ Ptree ; data parent双亲表示法的

8、结点结构双亲表示法 树及其双亲表示的存储结构 利用任一结点的双亲结点唯一的性质，可以方便地直接找到任一结点的双亲结点； 求结点的孩子结点时需要扫描整个数组。 数据结构14FGHIRABCDE R -10 A 01 B 02 C 03 D 14 E 15 F 36 G 67 H 68 I 69树的双亲表示法示例数组下标孩子表示法由于树中每个结点可能有多棵子树，使用多重链表：即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。多重链表表示法两种结点结构设计方案1. 定长结点结构（同构）定长结点结构（同构）指针域的个数等于树的度d d；链表结构简单，存在很多空链域，空间浪费明显；在一棵有n个结

9、点，度为k的树中必有n*(k-1)+1个空链域。数据结构15 data child1 child2 childd孩子表示法两种结点结构设计方案2. 不定不定长结点长结点结构（不同构）结构（不同构）每个结点指针域的个数等于该结点的度k；没有多余的指针域，节约存储空间，但操作不便。孩子表示法（复合链表结构） 把每个结点的孩子结点排列起来，以单链表单链表作存储结构，则 n 个结点有 n 个孩子链表(叶子的孩子链表为空表)； n 个头指针组成一个线性表，采用顺序存储结构(一维数组)。数据结构16 data k child1 child2 childk孩子表示法 数据结构类型定义如下：#define M

10、AX_NODE 100typedef struct listnode int childno ; /* 孩子结点编号 */ struct listno *next ;CTNode; /* 表结点结构 */typedef struct ElemType data ; CTNode *firstchild ;HNode; /* 头结点结构 */数据结构17 data firstchild(b) 头结点 childno next(a) 表结点孩子表示法typedef struct HNode nodesMAX_NODE ; int root; /* 根结点位置 */ int num ; /* 结点数

11、 */CLinkList; /* 头结点结构 */数据结构18789 35 012 6 0123456789MAX_NODE-1rootnumA B C D E F G H I R 49树的孩子链表存储结构FGHIRABCDE头结点表结点孩子兄弟表示法链表中结点的两个指针域分别指向结点的第一个孩子结点(firstchild)和下一个兄弟结点(nextsibling)。以二叉链表作为树的存储结构，又称二叉树表示法，或二叉链表表示法。结点类型定义如下：typedef struct Csnode ElemType data ; struct CSnode *firstchild, *nextsibl

12、ing;CSNode ; 数据结构19孩子兄弟表示法树及其孩子兄弟表示的存储结构数据结构20树及孩子兄弟存储结构(b) 树 FGRABCDE(c) 孩子兄弟存储结构 R A D C G B F E 孩子结点兄弟结点 firstchild data nextsibling(a) 结点结构第5讲 树和二叉树树的基本概念树的存储结构21数据结构初识二叉树对于在某个阶段都是两种结果的情形，比如开和关、0和1、真和假、上和下、对与错、正面与反面等，都适用一种特殊的树状结构来建模，叫做二叉树。 二叉树的定义 二叉树的性质 二叉树的存储结构数据结构22二叉树的定义二叉树 (Binary tree) 是 n

13、(n0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二叉树的定义是递归的。二叉树特点每个结点最多有最多有两棵子树，故不存在度大于2的结点；左子树和右子树是有顺序的，次序不能任意颠倒；即使树中某结点只有一棵子树，也要区分左、右子树。数据结构23树1树2同一棵树，不同的二叉树二叉树的基本形态 五种基本形态：数据结构24AAAA(a)(b)(c)(d)(e)(a) 空二叉树(b) 仅有根结点的二叉树(c) 右子树为空(d) 左子树为空(e) 左、右子树都不空思考1：有三个结点的树，有几种形态？思考2：有三个结点的二

14、叉树，有几种形态？特殊二叉树斜树所有的结点都只有左子树的二叉树叫左斜树；所有的结点都只有右子树的二叉树叫右斜树。特点：每一层只有一个结点，结点的个数与二叉树的深度相同。满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i (1in)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。数据结构25满二叉树一棵深度为 k且有(2k-1)个结点的二叉树称为满二叉树。 叶子只能出现在最下一层； 所有支结点都有左、右子树，即非叶子结点的度一定

15、是2； 同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。按层序编号按层序编号：对满二叉树的结点进行连续编号，规定从根结点开始，按“自上而下、自左至右”的原则进行。数据结构26894101151213614157213所有叶子在同一层上树的平衡完全二叉树深度为k、有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。深度为k 的满二叉树中，编号从1到n的前 n 个结点构成了一棵深度为k的完全二叉树，其中 2k-1 n2k-1 ；区分“完全”和“满”的差异，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。数据结构

16、27894101151213614157213894101151267213满二叉树完全二叉树894101151267213完全二叉树的特点若完全二叉树的深度为 k ，则所有的叶子结点都出现在第 k 层或 (k-1) 层。对于任一结点，如果其右子树的最大层次为 l，则其左子树的最大层次为 l 或 (l+1)。数据结构281362455674213非完全二叉树894101151267213完全二叉树深度为深度为4二叉树性质1 性质1：在二叉树的第i层上至多有2i-1个结点 (i1)。 证明：用数学归纳法证明。当i=1时：只有一个根结点，21-1 = 20 =1，命题成立。现假设当i1时，处在第i

17、-1层上至多有2(i-1)-1个结点，由归纳假设知，第i-1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i-1层上最大结点数的2倍。即 22i-22i-1 证毕数据结构29二叉树性质2 性质2：深度为k的二叉树至多有2k-1个结点（k1) 。 证明：深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和。由性质1知，二叉树的第1层、第2层 第k层上的结点数至多有： 20、21 2k-1 。 总的结点数至多有： 20+21+ +2k-1=2k-1 证毕数据结构30二叉树性质3 性质3：对任何一棵二叉树T，如果其叶子结点数为n0， 度为2的结点数为n2，则n0=n2+1。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，则有：N=n0+n1+n2再看二叉树中的分支数：除根结点外，其余每个结点都有唯一一个进入分支，而所有这些分支都是由度为1和2的结点射出的。设B为二叉树中的分支总数，则有：N=B+1 B n1+2 * n2