数据结构第07次课-树Appt课件

1、每课一贴：一个人去买鹦鹉，看到一只鹦鹉前标：此鹦鹉会两门语言，售价二百元。另一只鹦鹉前则标有：此鹦鹉会四门语言，售价四百元。该买哪只呢？两只都毛色光鲜，非常灵活可爱。这人转啊转，拿不定主意。结果突然发现一只老掉了牙的鹦鹉，毛色暗淡散乱，标价八百元。这人赶紧将老板叫来：这只鹦鹉是不是会说八门语言？店主说：不。这人奇怪了：那为什么又老又丑，又没有能力，会值这个数呢？店主回答：因为另外两只鹦鹉叫这只鹦鹉老板。这故事告诉我们，真正的领导人，不一定自己能力有多强，只要懂信任，懂放权，懂珍惜，就能团结比自己更强的力量，从而提升自己的身价。相反许多能力非常强的人却因为过于完美主义，事必躬亲，什么人都不如自己

2、，最后只能做最好的攻关人员，销售代表，成不了优秀的领导人。 数据结构课程的内容数据结构课程的内容第第6章章 树和二叉树（树和二叉树（ Tree & Binary Tree ）6.1 树的基本知识树的基本知识6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个特点：非线性结构，一个直接前驱，但可能有多个直接后继直接后继1:n1:n）6.1 树的基本知识树的基本知识1. 树的定义树的定义2. 若干术语若干术语3. 逻辑结构逻辑结构4.存储结构存储结构5. 树的运算

3、树的运算1. 树的定义树的定义注注1：过去许多书籍中都定义树为：过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是树树的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具有递归性，即树中还有树。：树的定义具有递归性，即树中还有树。由一个或多个由一个或多个(n0)(n0)结点组成的有限集合结点组成的有限集合T T，有，有且仅有一个结点称为根且仅有一个结点称为根rootroot），当），当n1n1时，其余的时，其余的结点分为结点分为m(m0)m(m0)个互不相交的有限集合个互不相交的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，被称作这个根的子

4、树。每个集合本身又是棵树，被称作这个根的子树 。2. 若干术语若干术语即上层的那个结点即上层的那个结点(直接前驱直接前驱) parent即下层结点的子树即下层结点的子树 (直接后继直接后继) child同一双亲下的同层结点孩子之间互称兄弟同一双亲下的同层结点孩子之间互称兄弟sibling即双亲位于同一层的结点但并非同一双亲即双亲位于同一层的结点但并非同一双亲cousin即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前

5、驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换左为第一）结点各子树从左至右有序，不能互换左为第一）结点各子树可互换位置。结点各子树可互换位置。2. 若干术语续）若干术语续）即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数有几个直接后继就是有几个直接后继就是几度，亦称几度，亦称“次数次数”）结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCG

6、EIDHFJMLK从根到该结点的层数根结点算第一层）从根到该结点的层数根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子除树根以外的结点也称为内部结点）除树根以外的结点也称为内部结点）所有结点度中的最大值所有结点度中的最大值Max各结点的度各结点的度）指所有结点中最大的层数指所有结点中最大的层数Max各结点的层次各结点的层次）问：右上图中的结点数问：右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4树的表示法有几种：树的表示法有几种：图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法左孩子右兄弟表示法左孩子右兄弟表示法

7、树的抽象数据类型定义参见教材树的抽象数据类型定义参见教材P118-119图形表示法：图形表示法：老师老师学生学生其他人员其他人员9999级级20002000级级 20192019级级20192019级级三峡大学电气学院三峡大学电气学院计算机系计算机系电子系电子系自控系自控系叶子叶子根根子树子树广义表表示法广义表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )根作为由子树森林组成的表的名字写在表的左边根作为由子树森林组成的表的名字写在表的左边ABCGEIDHFJMLK左孩子右兄弟表示法左孩子右兄弟表示法数据数据左孩子左孩

8、子 右兄弟ABCGEIDHFJMLK 树的抽象数据类型定义树的抽象数据类型定义ADT Tree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT Tree若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有15个个3. 树的逻

9、辑结构树的逻辑结构 ( (特点特点) )： 一对多一对多1:n1:n），有多个直接后继如家谱），有多个直接后继如家谱树、目录树等等），但只有一个根结点，树、目录树等等），但只有一个根结点，且子树之间互不相交。且子树之间互不相交。 4. 树的存储结构树的存储结构 讨论讨论1：树是非线性结构，该怎样存储？：树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。 讨论讨论3：树的链式存储方案应该怎样制定？：树的链式存储方案应该怎样制定？可规定为：从上至下、从左至右将树的结点依次存入内存。可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：复原困难不能唯

10、一复原就没有实用价值）。重大缺陷：复原困难不能唯一复原就没有实用价值）。讨论讨论2：树的顺序存储方案应该怎样制定？：树的顺序存储方案应该怎样制定？可用多重链表：一个前趋指针，可用多重链表：一个前趋指针，n n个后继指针。个后继指针。细节问题：树中结点的结构类型样式该如何设计？细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长还是还是“不等长不等长”？缺点：等长结构太浪费每个结点的度不一定相同）；缺点：等长结构太浪费每个结点的度不一定相同）； 不等长结构太复杂要定义好多种结构类型）。不等长结构太复杂要定义好多种结构类型）。解决思路：先研究最简单、最有规律的树，然后设

11、法把解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为这种简单的树。一般的树转化为这种简单的树。讨论讨论4：计算机如何实现各种不同进制的运算？：计算机如何实现各种不同进制的运算？ 实现思路：先研究最简单、最有规律的二进制运算规律，实现思路：先研究最简单、最有规律的二进制运算规律，然后设法把各种不同进制的运算转化二进制运算。然后设法把各种不同进制的运算转化二进制运算。讨论讨论5：树的存储可否借鉴这种思路呢？：树的存储可否借鉴这种思路呢？5. 树的运算树的运算 要明确：要明确：1. 普通树即多叉树若不转化为二叉树，则运普通树即多叉树若不转化为二叉树，则运算很难实现。算很难实现。2. 二

12、叉树的运算仍然是插入、删除、修改、查找、二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够排序等，但这些操作必须建立在对树结点能够“遍历遍历的基础上！的基础上！ （遍历（遍历指每个结点都被访问且仅访问一次，指每个结点都被访问且仅访问一次，不遗漏不重复）。不遗漏不重复）。本章重点：二叉树的表示和实现本章重点：二叉树的表示和实现6.2 6.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “ “叉叉” ” 的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

13、可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1. 二叉树的定义二叉树的定义2. 二叉树的性质二叉树的性质3. 二叉树的存储结构二叉树的存储结构（二叉树的运算见（二叉树的运算见6.3节）节）定义：是定义：是nn0个结点的有限集合，由一个根结点以及两个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成棵互不相交的、分别称为左子树和右子树的二叉树组成 。逻辑结构：逻辑结构： 一对二一对二1：2） 基本特征基本特征: 每个结点最多只有两棵子树不存在度大于每个结点最多只有两棵子树不存在度大于2的结点）；的结点）； 左子树和右子树次序不能颠倒有序树）。左子树和右子

14、树次序不能颠倒有序树）。基本形态：基本形态： 5种种/2种种讨论讨论1 1：第：第i i层的结点数至多是多少？层的结点数至多是多少？ 性质性质1: 1: 在二叉树的第在二叉树的第i i层上至多有层上至多有2i-12i-1个结点个结点i0i0）。）。性质性质2: 2: 深度为深度为k k的二叉树至多有的二叉树至多有2k-12k-1个结点个结点k0k0）。）。2i-12i-1个个提问：第提问：第i i层上至少有层上至少有 个结点？个结点？1 1讨论讨论2 2：深度为：深度为k k的二叉树，至多有多少个结点？的二叉树，至多有多少个结点？ 2k-12k-1提问：深度为提问：深度为k k时至少有时至少有

15、 个结点？个结点？k k讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？性质性质3: 3: 对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n2n2个，个，则叶子数则叶子数n0n0必定为必定为n2n21 1 （即（即n0=n2+1n0=n2+1）ABCGEIDHFJ满二叉树：一棵深度为满二叉树：一棵深度为k k 且有且有2k -12k -1个结点的二叉树。个结点的二叉树。 （特点：每层都（特点：每层都“充溢了结点）充溢了结点）完全二叉树：深度为完全二叉树：深度为k k 的，有的，有n n个结点个结点的二叉树，

16、当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与深度为深度为k k 的满二叉树中编号从的满二叉树中编号从1 1至至n n的结的结点一一对应。点一一对应。AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树深度为深度为4 4的完全二叉树的完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原！因为它们在顺序存储方式下可以复原！ 完全二叉树的特点就是，只有最后一层完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。叶子不满，且全部集中在左边。 这其实是顺序二叉树的含义。这其实是顺序二叉树的含义。对于两种

17、特殊形式的二叉树满二叉树和完全二叉树），对于两种特殊形式的二叉树满二叉树和完全二叉树），还特别具备以下还特别具备以下2 2个性质：个性质：性质性质4: 4: 具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为log2nlog2n1 1证明：根据性质证明：根据性质2 2，深度为，深度为k k的二叉树最多只有的二叉树最多只有2k-12k-1个结点，且个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数的总结点数n n位于位于k k层和层和k-1k-1层满二叉树容量之间，即：层满二叉树容量之间，即：2k-

18、1-1n2k-1 2k-1-1n2k-1 或或2k-1n2k2k-1n2k，三边同时取对数，于是有：三边同时取对数，于是有：k-1log2nk k-1log2nk 因为因为k k是整数，所以是整数，所以k= k= log2nlog2n+1+1性质性质5: 5: 对完全二叉树，若从上至下、从左至右编号，对完全二叉树，若从上至下、从左至右编号，则编号为则编号为i i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i2i，其右孩，其右孩子编号必为子编号必为2i2i1 1；其双亲的编号必为；其双亲的编号必为i/2i/2i i1 1 时时为根为根, ,除外）。除外）。 证明：对于第证明：对于第k k

19、层的中编号为层的中编号为i i的元素，的元素，在第在第k k层中前面有层中前面有x xi-2k-1i-2k-1个元素个元素在第在第k k层中后面有层中后面有y y2k-12k-11 1x x个元素，个元素，则其左孩子编号是：则其左孩子编号是：i+y+2x+1=i+2k-1-1-x+2x+1=i+2k-1+x=i+2k-1+i-2k-1=2ii+y+2x+1=i+2k-1-1-x+2x+1=i+2k-1+x=i+2k-1+i-2k-1=2i则其右孩子编号是：则其右孩子编号是：i+y+2x+2=2ii+y+2x+2=2i1 1对 于 左 右 孩 子 ， 其 双 亲 节 点 编 号 必 然 为对 于

20、 左 右 孩 子 ， 其 双 亲 节 点 编 号 必 然 为 i / 2 i / 2 (2i+1)/2=2i/2=i(2i+1)/2=2i/2=i3. 3. 深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度为深度为k k 的二叉树的结点总数，最多为的二叉树的结点总数，最多为 个。个。 ) )k-1 k-1 ) log2k ) log2k ) ) k k ) )k k课堂练习：课堂练习：1. 1. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深

21、度深度 ) ) 度度课堂讨论：课堂讨论： 二叉树是不是树的特殊情况？二叉树是不是树的特殊情况？答：不是！虽然二叉树也属于一种树结构，但它是另外单独定答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树，并非一般树的特例。它的子树有顺序规定，分为义的一种树，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。左子树和右子树。不能随意颠倒。：满二叉树和完全二叉树有什么区别？：满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-n-1 1层是满的，但最底层却允许在右边缺少连续若干个

22、结点。满层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。二叉树是完全二叉树的一个特例。课堂讨论：课堂讨论：Q2: Q2: 设一棵完全二叉树具有设一棵完全二叉树具有10001000个结点，则它有个结点，则它有 个叶个叶子结点，有子结点，有 个度为个度为2 2的结点，有的结点，有 个结点只有非空左子个结点只有非空左子树，有树，有 个结点只有非空右子树。个结点只有非空右子树。4894894884881 10 0Q1Q1：为什么要研究满二叉树和完全二叉树这两种特殊形式？：为什么要研究满二叉树和完全二叉树这两种特殊形式？A1A1：因为只有这两种形式可以实现顺序存储！：因为只有这两种形式可以实现顺序存储！由于最后一层叶子数为由于最后一层叶子数为489489个，是奇数，说明有个，是奇数，说明有1 1个结点只有非空个结点只有非空左子树；而完全二叉树中不可能出现非空右子树左子树；而完全二叉树中不可能出现非空右子树(0(0个个) )。A2A2：易求出总层数和末层叶子数。总层数：易求出总层数和末层叶子数。总层数k=k=log2nlog2n1 1 =10;=10;且前且前9 9层总结点数为层总