数据结构章节程内容ppt课件

1、数据构造课程的内容数据构造课程的内容第第6章章 树和二叉树树和二叉树 Tree & Binary Tree 6.1 树的根本概念树的根本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其运用赫夫曼树及其运用特点：非线性构造，一个直接前驱，但能够有多个特点：非线性构造，一个直接前驱，但能够有多个直接后继直接后继1 1：n n6.1 树的根本概念树的根本概念1. 树的定义树的定义2. 假设干术语假设干术语3. 逻辑构造逻辑构造4.存储构造存储构造5. 树的运算树的运算1. 树的定义树的定义注注1：过去许多书籍中都定义树为

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

3、树的表示法有几种：图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法左孩子右兄弟表示法左孩子右兄弟表示法这些表示法的表示图这些表示法的表示图参见教材参见教材P120P120树的笼统数据类型定义参见教材树的笼统数据类型定义参见教材P118-119图形表示法：图形表示法：教师教师学生学生其他人员其他人员20002000级级 20192019级级 20192019级级20192019级级太原科技大学太原科技大学经管经管应科应科外语外语叶子叶子根根子树子树广义表表示法广义表表示法( A ( B ( E ( K, L ), F ), C ( G ), D ( H

4、 ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边根作为由子树森林组成的表的名字写在表的左边左孩子右兄弟表示法左孩子右兄弟表示法数据数据左孩子左孩子 右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 树的笼统数据类型定义树的笼统数据类型定义见教材见教材P118-119P118-119ADT Tree数据对象数据对象D:数据关系数据关系R:根本操作根本操作 P：ADT Tree假设假设D为空集，那么称为空树；为空集，那么称为空树；/允许允许n=0假设假设D中仅含一个数据元素，那么中仅含一个数据元

5、素，那么R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系： root 独一独一 /关于根的阐明关于根的阐明 DjDk= /关于子树不相交的阐明关于子树不相交的阐明 /关于数据元素的阐明关于数据元素的阐明D是具有一样特性的数据元素的集合。是具有一样特性的数据元素的集合。/至少有至少有15个个2. 假设干术语假设干术语即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点孩子之间互称兄弟同一双亲下的同层结点孩子之间互称兄弟即双亲位于同一层的结点但并非同一双亲即双亲位于同一层的结点但并非同一双亲即从根

6、到该结点所经分支的一切结点即从根到该结点所经分支的一切结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换左为第一结点各子树从左至右有序，不能互换左为第一结点各子树可互换位置。结点各子树可互换位置。2. 假设干术语续假设干术语续即树的数据元素即树的数据元素结点挂接的子

7、树数结点挂接的子树数有几个直接后继就是有几个直接后继就是几度，亦称几度，亦称“次数次数结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJMLK从根到该结点的层数根结点算第一层从根到该结点的层数根结点算第一层即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点也称为内部结点的结点也称为内部结点一切结点度中的最大值一切结点度中的最大值Max各结点的度各结点的度指一切结点中最大的层数指一切结点中最大的层数Max各结点的层次各结点的层次问：右上图中的结点数问：右上图中的结点数 ；树的度；树的度 ；树

8、的深度；树的深度13133 34 43. 树的逻辑构造树的逻辑构造 ( (特点特点) )： 一对多一对多1:n1:n，有多个直接后继如家谱，有多个直接后继如家谱树、目录树等等，但只需一个根结点，树、目录树等等，但只需一个根结点，且子树之间互不相交。且子树之间互不相交。 4. 树的存储构造树的存储构造 讨论讨论1：树是非线性构造，该怎样存储？：树是非线性构造，该怎样存储？依然有顺序存储、链式存储等方式。依然有顺序存储、链式存储等方式。 讨论讨论3：树的链式存储方案应该怎样制定？：树的链式存储方案应该怎样制定？可规定为：从上至下、从左至右将树的结点依次存入内存。可规定为：从上至下、从左至右将树的结

9、点依次存入内存。艰苦缺陷：复原困难不能独一复原就没有适用价值。艰苦缺陷：复原困难不能独一复原就没有适用价值。讨论讨论2：树的顺序存储方案应该怎样制定？：树的顺序存储方案应该怎样制定？可用多重链表：一个前趋指针，可用多重链表：一个前趋指针，n n个后继指针。个后继指针。细节问题：树中结点的构造类型款式该如何设计？细节问题：树中结点的构造类型款式该如何设计？ 即应该设计成即应该设计成“等长还是等长还是“不等长？不等长？缺陷：等长构造太浪费每个结点的度不一定一样；缺陷：等长构造太浪费每个结点的度不一定一样； 不等长构造太复杂要定义好多种构造类型。不等长构造太复杂要定义好多种构造类型。处理思绪：先研讨

10、最简单、最有规律的树，然后设法把处理思绪：先研讨最简单、最有规律的树，然后设法把普通的树转化为简单树。普通的树转化为简单树。5. 树的运算树的运算 要明确：要明确：1. 普通树即多叉树假设不转化为二叉树，那普通树即多叉树假设不转化为二叉树，那么运算很难实现。么运算很难实现。2. 二叉树的运算依然是插入、删除、修正、查找、二叉树的运算依然是插入、删除、修正、查找、排序等，但这些操作必需建立在对树结点可以排序等，但这些操作必需建立在对树结点可以“遍历的根底上！遍历的根底上！遍历遍历指每个结点都被访问且仅访问一次，指每个结点都被访问且仅访问一次，不脱漏不反复。不脱漏不反复。本章重点：二叉树的表示和实

11、现本章重点：二叉树的表示和实现6.2 6.2 二叉树二叉树为何要重点研讨每结点最多只需两个为何要重点研讨每结点最多只需两个 “叉叉 的树？的树？二叉树的构造最简单，规律性最强；二叉树的构造最简单，规律性最强；可以证明，一切树都能转为独一对应的二叉树，不失普通性。可以证明，一切树都能转为独一对应的二叉树，不失普通性。1. 二叉树的定义二叉树的定义2. 二叉树的性质二叉树的性质3. 二叉树的存储构造二叉树的存储构造二叉树的运算见二叉树的运算见6.3节节定义：是定义：是nn0个结点的有限集合，由一个根结点以及两个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成棵互不

12、相交的、分别称为左子树和右子树的二叉树组成 。逻辑构造：逻辑构造： 一对二一对二1：2 根本特征根本特征: 每个结点最多只需两棵子树不存在度大于每个结点最多只需两棵子树不存在度大于2的结点；的结点； 左子树和右子树次序不能颠倒有序树。左子树和右子树次序不能颠倒有序树。根本形状：根本形状： 5种种/2种种二叉树的笼统数据类型定义见教材二叉树的笼统数据类型定义见教材P121-122P121-122ADT BinaryTree数据对象数据对象D:数据关系数据关系R:根本操作根本操作 P：ADT BinaryTree假设假设D=，那么，那么R= ；假设假设D，那么，那么R= H；存在二元关系：；存在二

13、元关系： root 独一独一 /关于根的阐明关于根的阐明 DjDk= /关于子树不相交的阐明关于子树不相交的阐明 /关于数据元素的阐明关于数据元素的阐明 /关于左子树和右子树的阐明关于左子树和右子树的阐明D是具有一样特性的数据元素的集合。是具有一样特性的数据元素的集合。/至少有至少有20个个讨论讨论1 1：第：第i i层的结点数至多是多少？层的结点数至多是多少？ 利用二进制性质可轻利用二进制性质可轻松求出松求出 性质性质1: 1: 在二叉树的第在二叉树的第i i层上至多有层上至多有2i-12i-1个结点个结点i0i0。性质性质2: 2: 深度为深度为k k的二叉树至多有的二叉树至多有2k-12

14、k-1个结点个结点k0k0。2i-12i-1个个讨论讨论2 2：深度为：深度为k k的二叉树，至多有多少个结点？的二叉树，至多有多少个结点？ 利用二进制性质可利用二进制性质可轻松求出轻松求出2k-12k-1讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？性质性质3: 3: 对于任何一棵二叉树，假设对于任何一棵二叉树，假设2 2度的结点数有度的结点数有n2n2个，那么叶子数个，那么叶子数n0n0必定为必定为n2n21 1 即即n0=n2+1n0=n2+1ABCGEIDHFJ对于两种特殊方式的二叉树满二叉树和完全二叉树，对于两种特殊方式的

15、二叉树满二叉树和完全二叉树，还特别具备以下还特别具备以下2 2个性质：个性质：性质性质4: 4: 具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为log2nlog2n1 1性质性质5: 5: 对完全二叉树，假设从上至下、从左至右编对完全二叉树，假设从上至下、从左至右编号，那么编号为号，那么编号为i i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i2i，其右孩子编号必为其右孩子编号必为2i2i1 1；其双亲的编号必为；其双亲的编号必为i/2i/2i i1 1 时为根时为根, ,除外。除外。 证明：根据性质证明：根据性质2 2，深度为，深度为k k的二叉树最多只需的二

16、叉树最多只需2k-12k-1个结点，且完全二叉树个结点，且完全二叉树的定义是与同深度的满二叉树前面编号一样，即它的总结点数的定义是与同深度的满二叉树前面编号一样，即它的总结点数n n位于位于k k层和层和k-1k-1层满二叉树容量之间，即层满二叉树容量之间，即 2k-1-1n2k-1 2k-1-1n2k-1 或或2k-1n2k2k-1n2k三边同时取对数，于是有：三边同时取对数，于是有：k-1log2nk k-1log2nk 由于由于k k是整数，所以是整数，所以k=log2n+1k=log2n+1可根据归纳法证明。可根据归纳法证明。满二叉树：一棵深度为满二叉树：一棵深度为k k 且有且有2k

17、 -12k -1个结点的二叉树。个结点的二叉树。 特点：每层都特点：每层都“充溢了结点充溢了结点完全二叉树：深度为完全二叉树：深度为k k 的，有的，有n n个结点个结点的二叉树，当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与深度为深度为k k 的满二叉树中编号从的满二叉树中编号从1 1至至n n的结的结点一一对应。点一一对应。AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树深度为深度为4 4的完全二叉树的完全二叉树ABCGEIDHFJ为何要研讨这两种特殊方式？为何要研讨这两种特殊方式？由于它们在顺序存储方式下可以复原！由于它们在顺序存储方式下可以复原！ 解释：

18、完全二叉树的特点就是，只需最后解释：完全二叉树的特点就是，只需最后一层叶子不满，且全部集中在左边。一层叶子不满，且全部集中在左边。 3. 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. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深度深度 ) )

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

20、的，但最底层却允许在右边短少延续假设干个结点。满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。课堂讨论：课堂讨论：Q1Q1：满二叉树和完全二叉树有什么区别？：满二叉树和完全二叉树有什么区别？A1A1：满二叉树是叶子一个也不少的树，而完全二叉树虽然前：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-n-1 1层是满的，但最底层却允许在右边短少延续假设干个结点。层是满的，但最底层却允许在右边短少延续假设干个结点。 满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。Q3: Q3: 设一棵完全二叉树具有设一棵完全二叉树具有10001000个结点，那么它有个结点，那么它

21、有 个个叶子结点，有叶子结点，有 个度为个度为2 2的结点，有的结点，有 个结点只需非空左个结点只需非空左子树，有子树，有 个结点只需非空右子树。个结点只需非空右子树。4894894884881 10 0Q2Q2：为什么要研讨满二叉树和完全二叉树这两种特殊方式？：为什么要研讨满二叉树和完全二叉树这两种特殊方式？A1A1：由于只需这两种方式可以实现顺序存储！：由于只需这两种方式可以实现顺序存储！由于最后一层叶子数为由于最后一层叶子数为489489个，是奇数，阐明有个，是奇数，阐明有1 1个结点只需非空个结点只需非空左子树；而完全二叉树中不能够出现非空右子树左子树；而完全二叉树中不能够出现非空右子

22、树(0(0个个) )。A3A3：易求出总层数和末层叶子数。总层数：易求出总层数和末层叶子数。总层数k=k=log2nlog2n 1 =10;1 =10;且前且前9 9层总结点数为层总结点数为29-1=511 (29-1=511 (完全二叉树的前完全二叉树的前k-1k-1层一定是层一定是满的满的) )所以末层叶子数为所以末层叶子数为1000-511=4891000-511=489个。个。请留意叶子结点总数请留意叶子结点总数末层叶子数！末层叶子数！还该当加上第还该当加上第k-1k-1层靠右边的层靠右边的0 0度结点个数。度结点个数。分析：末层的分析：末层的489489个叶子只占据了上层的个叶子只占

23、据了上层的245245个结点个结点489/2489/2 ) )上层上层k=9)k=9)右边的右边的0 0度结点数还有度结点数还有29-1-245=1129-1-245=11个！个！ 另一法：可先求另一法：可先求2 2度结点数度结点数, ,再由此得到叶子总数。再由此得到叶子总数。首先，首先，k-2k-2层的层的28-128-1255255个结点一定都是个结点一定都是2 2度的完全二叉度的完全二叉另外，末层叶子刚刚已求出为另外，末层叶子刚刚已求出为489489所对应的双亲也是度所对应的双亲也是度2 2， 共有共有489/2489/2 244244个。个。所以，全部所以，全部2 2度结点数为度结点数为255(k-2255(k-2层层) )244(k-1244(k-1层层)=499)=499个；个；总叶子数总叶子数2 2度结点数度结点数1=5001=500个。个。第第i i层上的满层上的满结点数为结点数为2i-12i-1所以，所以，全部叶子数全部叶子数489(489(末层末层) )11(k-111(k-1层层)=500)=500个。个。 度为度为2 2的结点叶子总数的结点叶子总数1=4991=499个。个。4. 4. 二叉树的存储构造二叉树的存储构造一、顺序存储构造一、顺序存储构造按二叉树的结