《数据结构章节程内容》由会员分享，可在线阅读，更多相关《数据结构章节程内容（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程的内容数据结构课程的内容1第第6章章 树和二叉树（树和二叉树（ Tree & Binary Tree ）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个直接后继（直接后继（1 1：n n）26.1 树的基本概念1. 树的定义树的定义2. 若干术语若干术语3. 逻辑结构逻辑结构4.存储结构存储结构5. 树的运算树的运算31. 树的定义树的定义注注1：过去许多书籍中都定义树为过去许
2、多书籍中都定义树为n1，曾经有曾经有“空树不是空树不是树树”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具有树的定义具有递归性递归性，即树中还有树。，即树中还有树。由一个或多个由一个或多个( (n0n0) )结点组成的有限集合结点组成的有限集合T T，有有且仅有且仅有一个结点称为根一个结点称为根（rootroot），），当当n1n1时，其余的时，其余的结点分为结点分为m(m0)m(m0)个个互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，被称作这个根的每个集合本身又是棵树，被称作这个根的子树子树 。4树的表示法有几种：树
3、的表示法有几种：图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法左孩子右兄弟表示法左孩子右兄弟表示法这些表示法的示意图这些表示法的示意图参见教材参见教材P120P120树的抽象数据类型定义树的抽象数据类型定义参参见教材见教材P118-119P118-1195图形表示法：图形表示法：教师教师学生学生其他人员其他人员20002000级级 20012001级级 20022002级级20032003级级太原科技大学太原科技大学经管经管应科应科外语外语叶子叶子根根子树子树6广义表表示法广义表表示法( A ( B ( E ( K, L ), F ), C ( G
4、 ), D ( H ( M ), I, J ) ) 根作为根作为由子树森林组成的由子树森林组成的表的名字写在表的左边表的名字写在表的左边7左孩子右兄弟表示法左孩子右兄弟表示法A AB BC CD DE EF FGGHHI IJ JKKL LMM数据数据左孩子左孩子 右兄弟右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )8 树的抽象数据类型定义树的抽象数据类型定义（见教材（见教材P118-P118-119119）ADT Tree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT Tree若若D为空集，则
5、称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有15个个92. 若干术语若干术语即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩
6、子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点
7、各子树可互换位置。结点各子树可互换位置。102. 若干术语（续）若干术语（续）即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数（有几个直接后继就是几度，（有几个直接后继就是几度，亦称亦称“次数次数”）结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各
8、结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4113. 树的逻辑结构树的逻辑结构 ( (特点特点) )： 一对多（一对多（1:n1:n），），有多个直接后继（如家谱有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且树、目录树等等），但只有一个根结点，且子树之间互不相交子树之间互不相交。 4. 树的存储结构树的存储结构 讨论讨论1：树是非线性结构，该怎样存储？树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等
9、方式。 12讨论讨论3：树的树的链式存储链式存储方案应该怎样制定？方案应该怎样制定？可规定为：可规定为：从上至下、从左至右从上至下、从左至右将树的结点依次存入内存。将树的结点依次存入内存。重大缺陷：重大缺陷：复原困难（不能唯一复原就没有实用价值）。复原困难（不能唯一复原就没有实用价值）。讨论讨论2：树的树的顺序存储顺序存储方案应该怎样制定？方案应该怎样制定？可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n n个后继指针。个后继指针。细节问题：细节问题：树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？缺
10、点：缺点：等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。解决思路：解决思路：先研究最简单、最有规律的树，然后设法把先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。一般的树转化为简单树。二叉树二叉树二叉树二叉树135. 树的运算树的运算 要明确：要明确：1. 普普通通树树（即即多多叉叉树树）若若不不转转化化为为二二叉叉树树，则则运运算很难实现。算很难实现。2. 二二叉叉树树的的运运算算仍仍然然是是插插入入、删删除除、修修改改、查查找找、排排序序等等，但但这这些些
11、操操作作必必须须建建立立在在对对树树结结点点能能够够“遍历遍历”的基础上！的基础上！（遍遍历历指指每每个个结结点点都都被被访访问问且且仅仅访访问问一一次次，不遗漏不重复）。不遗漏不重复）。本章重点：二叉树的表示和实现本章重点：二叉树的表示和实现146.2 6.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “ “叉叉” ” 的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1. 二叉树的定义二叉树的定义2. 二叉树的性质二叉树的
12、性质3. 二叉树的二叉树的存存储结构储结构（二叉树的运算二叉树的运算见见6.3节节）151. 1. 1. 1. 二叉树的定义二叉树的定义二叉树的定义二叉树的定义定义：定义：是是n（n0）个结点的有限集合，由一个根结点以及两个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为棵互不相交的、分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成 。逻辑结构：逻辑结构： 一对二（一对二（1：2） 基本特征基本特征: 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）； 左子树和右子树次序不能颠倒（有序树）。左子树和右子树次序不能颠倒（有序
13、树）。基本形态：基本形态： 问：具有问：具有问：具有问：具有3 3 3 3个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？个结点的二叉树可能有几种不同形态？普通树呢？ 5种种/2种种16二叉树的抽象数据类型定义二叉树的抽象数据类型定义（见教材（见教材P P121-122121-122）ADT BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则，则R= ；若若D，则，则R= H；存在二元关系：存在二元关系： root 唯一唯一 /关于根的说明
14、关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明 /关于左子树和右子树的说关于左子树和右子树的说明明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有20个个172. 2. 2. 2. 二叉树的性质二叉树的性质二叉树的性质二叉树的性质 (3+2)(3+2)(3+2)(3+2)讨论讨论1 1：第：第i i层的结点数至多是多少？层的结点数至多是多少？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出） 性质性质1: 1: 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2 2 2i-1i-1i-1
15、i-1个结点（个结点（i0i0）。）。性质性质2: 2: 深度为深度为k k的二叉树至多有的二叉树至多有2 2 2 2k k k k-1-1-1-1个结点（个结点（k0k0）。）。2 2i-1i-1个个讨论讨论2 2：深度为：深度为k k的二叉树，至多有多少个结点？的二叉树，至多有多少个结点？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出）2 2k k-1-118讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗的结点数之间有关系吗？性质性质3: 3: 对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个，则叶
16、子数（则叶子数（n n0 0）必定为必定为n n2 21 1 （即（即n0=n2+1）证明：证明：证明：证明： 二叉树中全部结点数二叉树中全部结点数nn0+n1+n2( (叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数) )又又又又二叉树中全部结点数二叉树中全部结点数nB+1 ( ( 总分支数根结点总分支数根结点 ) ) （除根结点外，每个结点必有一个直接前趋，即一个分支）（除根结点外，每个结点必有一个直接前趋，即一个分支）而而而而 总分支数总分支数B= n1+2n2 (1(1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个) )三式联立可得：三
17、式联立可得：三式联立可得：三式联立可得： n0+n1+n2= n1+2n2 +1, 即即n0=n2+1实际意义：实际意义：叶子数叶子数2 2度结点数度结点数1 1ABCGEIDHFJ19对于两种特殊形式的二对于两种特殊形式的二叉叉树（树（满二叉树和完全二叉树满二叉树和完全二叉树），），还特别具备以下还特别具备以下2 2个性质：个性质：性质性质4: 4: 具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为loglog2 2nn1 1性质性质5: 5: 对完全二叉树，若从上至下、从左至右编号，则对完全二叉树，若从上至下、从左至右编号，则编号为编号为i 的结点，其左孩子编号必为的
18、结点，其左孩子编号必为2i，其右孩子编号必其右孩子编号必为为2i1；其双亲的编号必为其双亲的编号必为i/2（i1 时为根时为根, ,除外除外）。）。 证证明明：根根据据性性质质2 2，深深度度为为k k的的二二叉叉树树最最多多只只有有2 2k k-1-1个个结结点点，且且完完全全二二叉叉树树的的定定义义是是与与同同深深度度的的满满二二叉叉树树前前面面编编号号相相同同，即即它它的的总总结结点点数数n n位位于于k k层层和和k-1k-1层满二叉树容量之间，即层满二叉树容量之间，即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n n 2 2k k三边同时取对数，于是有
19、：三边同时取对数，于是有：k-1logk-1log2 2nk nk 因为因为k k是整数，所以是整数，所以k=logk=log2 2n+1n+1可根据归纳法证明。可根据归纳法证明。20满二叉树：满二叉树：一棵深度为一棵深度为k 且有且有2k -1个结点的二叉树。个结点的二叉树。 （特点：每层都（特点：每层都“充满充满”了结点了结点）完全二叉树：完全二叉树：深度为深度为k 的的，有有n个结点个结点的二叉树，当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与深度为深度为k 的满二叉树中编号从的满二叉树中编号从1至至n的结的结点一一对应。点一一对应。AOBCGEKDJFIHNML深度为深度为
20、4 4的满二叉树的满二叉树深度为深度为4 4的的完全二叉树完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原！因为它们在顺序存储方式下可以复原！ 解释：完全二叉树的特点就是，只有最后解释：完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。一层叶子不满，且全部集中在左边。 213. 3. 深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度为深度为k 的二叉树的结点总数，最多为的二叉树的结点总数，最多为 个。个。 ) )k-1k-1 )
21、log) log2 2k k ) ) k k ) )k k课堂练习：课堂练习：1. 1. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深度深度 ) ) 度度课堂讨论：课堂讨论： 二叉树是不是树的特殊情况？二叉树是不是树的特殊情况？答答：不不是是！虽虽然然二二叉叉树树也也属属于于一一种种树树结结构构，但但它它是是另另外外单单独独定定义义的的一一种种树树，并并非非一一般般树树的的特特例例。它它的的子子树树有有顺顺序序规规定定，分分为为左左子子树树和和右右子子树树。不不能能随随意颠倒。意颠倒。：满二叉树和完全二叉树有什么区别？满二叉树
22、和完全二叉树有什么区别？答答：满满二二叉叉树树是是叶叶子子一一个个也也不不少少的的树树，而而完完全全二二叉叉树树虽虽然然前前n-1n-1层层是是满满的的，但但最最底底层层却却允允许许在在右右边边缺缺少少连连续续若若干干个个结结点点。满满二二叉叉树树是是完完全全二二叉叉树树的的一一个特例。个特例。22课堂讨论：课堂讨论：Q1Q1：满二叉树和完全二叉树有什么区别？满二叉树和完全二叉树有什么区别？A1A1：满满二二叉叉树树是是叶叶子子一一个个也也不不少少的的树树，而而完完全全二二叉叉树树虽虽然然前前n-n-1 1层是满的，但最底层却允许在右边缺少连续若干个结点。层是满的，但最底层却允许在右边缺少连续
23、若干个结点。 满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。Q3: Q3: 设一棵完全二叉树具有设一棵完全二叉树具有10001000个结点，则它有个结点，则它有 个叶个叶子结点，有子结点，有 个度为个度为2 2的结点，有的结点，有 个结点只有非空左子个结点只有非空左子树，有树，有 个结点只有非空右子树。个结点只有非空右子树。4894894884881 10 0Q2Q2：为什么要研究满二叉树和完全二叉树这两种特殊形式？为什么要研究满二叉树和完全二叉树这两种特殊形式？A1A1：因为只有这两种形式可以实现顺序存储！因为只有这两种形式可以实现顺序存储！由于最后一层叶子数为由于最后一层
24、叶子数为489489个，是个，是奇数奇数，说明有，说明有1 1个结点只有非空个结点只有非空左子树；而完全二叉树中不可能出现非空右子树左子树；而完全二叉树中不可能出现非空右子树(0(0个个) )。A3A3：易求出总层数和末层叶子数。总层数易求出总层数和末层叶子数。总层数k=k= log2n 1 = =1010; ;且前且前9 9层总结点数为层总结点数为2 29 9-1=-1=511511 ( (完全二叉树的前完全二叉树的前k-1k-1层肯定是满的层肯定是满的) )所以末层叶子数为所以末层叶子数为1000-511=1000-511=489489个。个。23请注意叶子结点总数请注意叶子结点总数末层叶
25、子数末层叶子数！还应当加上第还应当加上第k-1k-1层（靠右边）的层（靠右边）的0 0度结点个数。度结点个数。分析：分析：末层的末层的489489个叶子只占据了上层的个叶子只占据了上层的245245个结点（个结点（ 489/2489/2 ) )上层（上层（k=9)k=9)右边的右边的0 0度结点数还有度结点数还有2 29-19-1-245=-245=1111个！个！ 另一法：另一法：可先求可先求2 2度结点数度结点数, ,再由此得到叶子总数。再由此得到叶子总数。首先，首先，k-2层的层的2 28 8-1-1（255255）个结点肯定都是）个结点肯定都是2 2度的度的（完全二叉）（完全二叉）另外
26、，末层叶子（刚才已求出为另外，末层叶子（刚才已求出为489489）所对应的双亲也是度）所对应的双亲也是度2 2， （共有（共有 489/2489/2 244244个）。个）。所以，全部所以，全部2 2度结点数为度结点数为255255( (k-2层层) )244244( (k-1层层) )= =499499个；个；总叶子数总叶子数2 2度结点数度结点数1=1=500500个。个。第第i i层上的满层上的满结点数为结点数为2 2i-1i-1所以，所以，全部叶子数全部叶子数489489( (末层末层) )1111(k-1(k-1层层) )= =500500个。个。 度为度为2 2的结点的结点叶子总数
27、叶子总数1 1= =499499个。个。244. 4. 二叉树的存储结构二叉树的存储结构一、顺序存储结构一、顺序存储结构按按二二叉叉树树的的结结点点“自自上上而而下下、从从左左至至右右”编编号号，用用一组连续的存储单元存储。一组连续的存储单元存储。A AB BC CD DE EF FG GH HI I123456789A AB BC CGGE EI ID DHHF F问：顺序存储后能否复原成唯一对应的二叉树形状？问：顺序存储后能否复原成唯一对应的二叉树形状？答：答：若是完全若是完全/ /满二叉树则可以做到唯一复原。满二叉树则可以做到唯一复原。 而且有规律：下标值为而且有规律：下标值为i i的双
28、亲，其左孩子的下标值必为的双亲，其左孩子的下标值必为2i2i，其右孩子的下标值必为其右孩子的下标值必为2i2i1 1（即性质即性质5 5） 例如，对应例如，对应22的两个孩子必为的两个孩子必为44和和5,5,即即B B的左孩子必的左孩子必是是D,D,右孩子必为右孩子必为E E。T0T0一一般不用般不用25讨论：讨论：不是完全二叉树怎么办？不是完全二叉树怎么办？答：答：一律转为完全二叉树！一律转为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点虚结点”，其内容为空。，其内容为空。A AB B C C D D E E123456789.16ABECD缺点：缺点：
29、浪费空间；浪费空间；插入、删除不便插入、删除不便 26二、链式存储结构二、链式存储结构用二叉链表即可方便表示。用二叉链表即可方便表示。datadataleft_childleft_childright_childright_childdatadataleft_childleft_childright_childright_child二叉树结点数据类型定义：二叉树结点数据类型定义：typedef struct node *tree_pointer;typedef struct node int data; tree_pointer left_child, right_child; node;一般从根结点开始存储。一般从根结点开始存储。（相应地，访问树中结点时（相应地，访问树中结点时也只能从根开始）也只能从根开始）注：注：如果需要倒查某结点的如果需要倒查某结点的双亲，可以再增加一个双亲双亲，可以再增加一个双亲域（直接前趋）指针，将二域（直接前趋）指针，将二叉链表变成三叉链表。叉链表变成三叉链表。27例：例： ABECD A AB B D D C C E E 28
