第6章树和二叉树第6章A

《第6章树和二叉树第6章A》由会员分享，可在线阅读，更多相关《第6章树和二叉树第6章A（32页珍藏版）》请在金锄头文库上搜索。

1、1,第5章 数组和广义表（Arrays & Lists）,5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构,2,2、广义表特点：,有次序性 有长度 有深度 可递归 可共享,一个直接前驱和一个直接后继 表中元素个数 表中括号的重数 自己可以作为自己的子表 可以为其他广义表所共享,特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。,3,介绍两种特殊的基本操作： GetHead( L) 取表头(可能是原子或列表); GetTail(L ) 取表尾(一定是列表) 。,广义表的抽象数据类型定义见教材P107-

2、108,4,1. GetTail【(b, k, p, h)】 ; 2. GetHead【( (a,b), (c,d) )】 ; 3. GetTail【( (a,b), (c,d) )】 ; 4. GetTail【 GetHead【(a,b),(c,d)】 ;,例：求下列广义表操作的结果（严题集5.10）,(k, p, h),（b）,5. GetTail【（e）】 ; 6. GetHead 【 ( ( ) )】 . 7. GetTail【 ( ( ) ) 】 .,( ),(a,b),( ),( ),(c,d),5,5.5 广义表的存储结构,由于广义表的元素可以是不同结构（原子或列表），难以用顺序

3、存储结构表示 ，通常用链式结构，每个元素用一个结点表示。,1.原子结点：通常设2个域,注意：列表的“元素”还可以是列表，故结点有两种形式：,2.表结点：通常设3个域,指向子表,指向下一结点,6, C =( a ,( b , c , d ) ),例：, E=(a, E),第4-5章自测卷习题解答,7,数据结构课程的内容,8,第6章 树和二叉树（ Tree & Binary Tree ）,6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用,特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）,9,6.1 树的基本概念,1. 树

4、的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,10,1. 树的定义,注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即树中还有树。,由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树 。,11,树的表示法有几种：,图形表示法 嵌套集合表示法 广义表表示法 目录表示法 左孩子右兄弟表示法,这些表示法的示意图参见教材P120,树的抽象数据类型定义参见教材P118-119

5、,12,图形表示法：,大连海事大学,叶子,根,子树,13,广义表表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边,麻烦问题：应当开设多少个链域?,14,左孩子右兄弟表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ),15,树的抽象数据类型定义,（见教材P118-119）,ADT Tree 数据对象D: 数据关系R: 基本操作 P： ADT Tree,若D为空集，则称为空树；/允许n=0 若D中仅含一个数

6、据元素，则R为空集； 其他情况下的R存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说明,D是具有相同特性的数据元素的集合。,/至少有15个,16,2. 若干术语,即上层的那个结点(直接前驱) 即下层结点的子树的根(直接后继) 同一双亲下的同层结点（孩子之间互称兄弟） 即双亲位于同一层的结点（但并非同一双亲） 即从根到该结点所经分支的所有结点 即该结点下层子树中的任一结点,根 叶子 森林 有序树 无序树,即根结点(没有前驱) 即终端结点(没有后继) 指m棵不相交的树的集合(例如删除A后的子树个数),双亲 孩子 兄弟 堂兄弟 祖先 子孙,结点各

7、子树从左至右有序，不能互换（左为第一） 结点各子树可互换位置。,17,2. 若干术语（续）,即树的数据元素 结点挂接的子树数（有几个直接后继就是几度，亦称“次数”）,结点 结点的度 结点的层次 终端结点 分支结点,树的度 树的深度 (或高度),从根到该结点的层数（根结点算第一层） 即度为0的结点，即叶子 即度不为0的结点（也称为内部结点）,所有结点度中的最大值（Max各结点的度） 指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数 ；树的度 ；树的深度,13,3,4,18,3. 树的逻辑结构,(特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点

8、，且子树之间互不相交。,4. 树的存储结构,讨论1：树是非线性结构，该怎样存储？ 仍然有顺序存储、链式存储等方式。,19,讨论3：树的链式存储方案应该怎样制定？,可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难（不能唯一复原就没有实用价值）。,讨论2：树的顺序存储方案应该怎样制定？,可用多重链表：一个前趋指针，n个后继指针。 细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？ 缺点：等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。,解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。

9、,二叉树,20,5. 树的运算,要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！ （遍历指每个结点都被访问且仅访问一次，不遗漏不重复）。,本章重点：二叉树的表示和实现,21,6.2 二叉树,为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构,（二叉树的运算见6.3节）,22,1. 二叉树的定义,定义：是n（n0）个结点

10、的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1：2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。 基本形态：,问：具有3个结点的二叉树可能有几种不同形态？普通树呢？,5种/2种,23,二叉树的抽象数据类型定义（见教材P121-122）,ADT BinaryTree 数据对象D: 数据关系R: 基本操作 P： ADT BinaryTree,若D=，则R= ； 若D，则R= H；存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说

11、明 /关于左子树和右子树的说明,D是具有相同特性的数据元素的集合。,/至少有20个,24,2. 二叉树的性质 (3+2),讨论1：第i层的结点数至多是多少？ （利用二进制性质可轻松求出）,性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。,性质2: 深度为k的二叉树至多有2k-1个结点（k0）。,2i-1个,提问：第i层上至少有 个结点？,1,讨论2：深度为k的二叉树，至多有多少个结点？ （利用二叉树性质1可轻松求出）,2k-1,提问：深度为k时至少有 个结点？,k,25,讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？,性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子

12、数（n0）必定为n21 （即n0=n2+1）,证明： 二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数) 又二叉树中全部结点数nB+1 ( 总分支数根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个) 三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1 实际意义：叶子数2度结点数1,26,对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：,性质4: 具有n个结点的完全二叉树的深度必为log2n1,性质5: 对完全二叉树，若从上至下、从左至右

13、编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i1；其双亲的编号必为i/2（i1 时为根,除外）。,证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1n2k-1 或2k-1n2k 三边同时取对数，于是有：k-1log2nk 因为k是整数，所以k=log2n+1,可根据归纳法证明。,27,满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点）,完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为

14、k 的满二叉树中编号从1至n的结点一一对应。,为何要研究这两种特殊形式？ 因为它们在顺序存储方式下可以复原！,刘解释：完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。 这其实是顺序二叉树的含义。在图论概念中的“完全二叉树”是指n1=0的情况。,28,3. 深度为9的二叉树中至少有 个结点。 )9 )8 ) )91,2.深度为k 的二叉树的结点总数，最多为 个。 )k-1 ) log2k ) k )k,课堂练习： 1. 树中各结点的度的最大值称为树的 。 ) 高度 ) 层次 ) 深度 ) 度,课堂讨论：, 二叉树是不是树的特殊情况？ 答：不是！虽然二叉树也属于一种树结构，但它是另外

15、单独定义的一种树，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。 ：满二叉树和完全二叉树有什么区别？ 答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。,29,4. 二叉树的存储结构,一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,A B C D E F G H I,问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5） 例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0一般不用,30,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。