第6章树和二叉树A

1、1 （共（共4题）：题）：4.8 4.10 4. 30 4.31 （共（共2题）：题）：5.18 5.30 下周一交下周一交 2 数据结构课程的内容数据结构课程的内容 3 第第1章章 绪论绪论 第第2章章 线性表线性表 第第3章章 栈和队列栈和队列 第第4章章 串串 第第5章章 数组和广义表数组和广义表 第第6 6章章 树和二叉树树和二叉树 第第7章章 图图 第第9章章 查找查找 第第10章章 排序排序 目目 录录 4 第第6 6章章 树和二叉树树和二叉树（Tree & Binary Tree） 6.1 树的基本概念树的基本概念 6.2 二叉树二叉树 6.3 遍历二叉树和线索二叉树遍历二叉树和

2、线索二叉树 6.4 树和森林树和森林 6.5 赫夫曼树及其应用赫夫曼树及其应用 特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个 直接后继。直接后继。（一对多或（一对多或1:1:n n） 二叉树的定义、二叉树的定义、 性质和存储结构性质和存储结构 二叉树的运算二叉树的运算 5 6.16.1 树的基本概念 6.1.1 树的定义树的定义 6.1.2 若干术语若干术语 6.1.3 逻辑结构逻辑结构 6.1.4 存储结构存储结构 6.1.5 树的运算树的运算 6 注注1：过去许多书籍中都定义树为过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是 树树

3、”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。 注注2：树的定义具有树的定义具有递归性递归性，即，即“树中还有树树中还有树”。 由一个或多个由一个或多个( (n0n0) )结点组成的有限集合结点组成的有限集合T T，有且仅有，有且仅有一一 个结点称为根个结点称为根（rootroot），），当当n1n1时，其余的结点分为时，其余的结点分为m m(m0)(m0)个个 互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，。每个集合本身又是棵树， 被称作这个根的被称作这个根的子树子树 。 7 即上层的那个结点即上层的那个结点(直接前驱直接前驱) 即

4、下层结点的子树的根即下层结点的子树的根(直接后继直接后继) 同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟） 即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲） 即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点 即该结点下层子树中的任一结点即该结点下层子树中的任一结点 A BC GEI D HFJ FLK 根根 叶子叶子 森林森林 有序树有序树 无序树无序树 即根结点即根结点(没有前驱没有前驱) 即终端结点即终端结点(没有后继没有后继) 指指m棵不相交的树的集棵不相交的树的集 合合(例如删除例如删除A后的子树个数后的

5、子树个数) 双亲双亲 孩子孩子 兄弟兄弟 堂兄弟堂兄弟 祖先祖先 子孙子孙 结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一） 结点各子树可互换位置。结点各子树可互换位置。 8 即树的数据元素即树的数据元素 结点挂接的子树数结点挂接的子树数 结点结点 结点的度结点的度 结点的层次结点的层次 终端结点终端结点 分支结点分支结点 树的度树的度 树的深度树的深度 (或高度或高度) A BC GEI D HFJ FLK 从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层） 即度为即度为0的结点，即叶子的结点，即叶子 即度不为即度不为0的结点（也

6、称为内部结点）的结点（也称为内部结点） 所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度） 指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次） 问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4 （有几个直接后继就是几度，亦称（有几个直接后继就是几度，亦称“次数次数”） 9 自学：树的抽象数据类型定义自学：树的抽象数据类型定义（见教材（见教材P118-119P118-119） ADT Tree 数据对象数据对象D: 数据关系数据关系R: 基本操作基本操作 P： ADT Tree D是具有相同特

7、性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0 若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集； 其他情况下的其他情况下的R存在二元关系：存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明 /至少有至少有15个，如求树深，求某结点的双亲个，如求树深，求某结点的双亲 10 一对多（一对多（1:n1:n），），有多个直接后继（如家谱有多个直接后继（如家谱 树、目录树等等），但只有一个根结点，树、目录树等

8、等），但只有一个根结点， 且且子树之间互不相交。子树之间互不相交。 讨论讨论1：树是非线性结构，该怎样存储？树是非线性结构，该怎样存储？ 特点：特点： 仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。 11 讨论讨论3：树的树的链式存储链式存储方案应该怎样制定？方案应该怎样制定？ 复原困难复原困难 可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n n个后继指针。个后继指针。 细节问题：细节问题： 树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？ 缺点：缺点： 等长结构太浪费（每个结点的

9、度不一定相同）；等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。 先研究最简单、最有规律的树，然先研究最简单、最有规律的树，然 后设法把一般的树转化为简单树。后设法把一般的树转化为简单树。 可规定为：可规定为： 从上至下、从左至右将树的结点依次存入内存。从上至下、从左至右将树的结点依次存入内存。 重大缺陷：重大缺陷： 解决思路：解决思路： 不能唯一复原就没有实用价值！不能唯一复原就没有实用价值！ 讨论讨论2：树的树的顺序存储顺序存储方案应该怎样制定？方案应该怎样制定？ 补充：树的补充：树的5种表示法：种表示法： v

10、 图形表示法图形表示法 v 嵌套集合表示法嵌套集合表示法 v 广义表表示法广义表表示法 v 凹入表示法凹入表示法 v 左孩子右兄弟表示法左孩子右兄弟表示法 13 教师教师学生学生其他人员其他人员 20012001级级 20022002级级 20032003级级20042004级级 华中科技大学华中科技大学 计算机系计算机系电信系电信系自控系自控系 叶子叶子 根根 子树子树 14 15 ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 约定：约定： 根根作为由子树森林组成的作为由子树森林组成的表的名字写在表的左边表的名字写在表的左

11、边 16 又称目录表示法又称目录表示法 17 datalink 1 link 2 .link n. 树结点的结构：树结点的结构： 困惑困惑：构造树的结点时构造树的结点时 应当开多少个链域应当开多少个链域? ? 18 data 左孩子左孩子 右兄弟右兄弟 多叉树转为多叉树转为 了二叉树了二叉树 19 要明确：要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难普通树（即多叉树）若不转化为二叉树，则运算很难 实现。实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序二叉树的运算仍然是插入、删除、修改、查找、排序 等，但这些操作必须建立在等，但这些操作必须建立在对树结点能够对树结点

12、能够“遍历遍历”的的 基础上！基础上！ 本章重点：本章重点： 二叉树的表示和实现二叉树的表示和实现 20 6.2 二叉树二叉树 为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “ “叉叉” ” 的树？的树？ 二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，可以证明，所有树都能转为唯一对应的二叉树， 不失一般性。不失一般性。 6.2.1 二叉树的定义二叉树的定义 6.2.2 二叉树的性质二叉树的性质 6.2.3 二叉树的存储结构二叉树的存储结构 注：二叉树的运算见注：二叉树的运算见6.36.3节节遍历遍历 21 定义：

13、定义：是是n（n0）个结点的有限集合，由一个根结点以及两）个结点的有限集合，由一个根结点以及两 棵互不相交的、分别称为棵互不相交的、分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成 。 逻辑结构：逻辑结构： 一对二（一对二（1:2） 基本特征基本特征: 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）； 左子树和右子树左子树和右子树次序不能颠倒次序不能颠倒。 基本形态：基本形态： 一般一般 的树的树 有几有几 种？种？ 22 二叉树的抽象数据类型定义二叉树的抽象数据类型定义（见教材（见教材P P121-122121-122） AD

14、T BinaryTree 数据对象数据对象D: 数据关系数据关系R: 基本操作基本操作 P： ADT BinaryTree D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D=，则，则R= ； 若若D，则，则R= H；存在二元关系：；存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明 /关于左子树和右子树的说明关于左子树和右子树的说明 /至少有至少有20个，如返回某结点的左孩子，个，如返回某结点的左孩子， 或中序遍历，等等或中序遍历，等等 23 讨论讨论1 1：第

15、：第i i层的结点数最多是多少？层的结点数最多是多少？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出） 性质性质1: 1: 性质性质2: 2: 再提问：第再提问：第i i层上至少有层上至少有 个结点？个结点？1 1 讨论讨论2 2：深度为：深度为k k的二叉树，最多有多少个结点？的二叉树，最多有多少个结点？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出） 24 性质性质3: 3: 对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个， 则叶子数（则叶子数（n n0 0）必定为必定为n n2 21 1 （即（即n0=n2+1） 二叉树中

16、全部结点数二叉树中全部结点数nn0+n1+n2( (叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数) ) 二叉树中全部结点数二叉树中全部结点数nB+1 ( ( 总分支数根结点总分支数根结点 ) ) （除根结点外，每个结点必有一个直接前趋，即一个分支）（除根结点外，每个结点必有一个直接前趋，即一个分支） 总分支数总分支数B= n1+2n2 (1(1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个) ) n0+n1+n2= n1+2n2 +1, 即即n0=n2+1 讨论讨论3 3：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？

17、的结点数之间有关系吗？ 25 3. 3. 深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。 ) )9 9 ) )8 8 ) ) ) )9 91 1 2.2.深度为的二叉树的结点总数，最多为深度为的二叉树的结点总数，最多为 个。个。 ) )k-1 k-1 ) log) log2 2k k ) ) k k ) )k k 1. 1. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深度深度 ) ) 度度 D C C 课堂练习：课堂练习： 26 证明：证明：根据性质根据性质2 2，深度为深度为k k的二叉树最多只有的二叉

18、树最多只有2 2k k-1-1个结点，且个结点，且 完全二叉树的定义是与同深度的满二叉树前面编号相同，即它完全二叉树的定义是与同深度的满二叉树前面编号相同，即它 的总结点数的总结点数n n位于位于k k层和层和k-1k-1层满二叉树容量之间，层满二叉树容量之间， 即即 2 2k-1 k-1-1n2 -1n2k k-1 -1 或或2 2k-1 k-1n2 n2k k 三边同时取对数，于是有：三边同时取对数，于是有：k-1logk-1log2 2nk nk 因为因为k k是整数，所以是整数，所以 k=k= loglog2 2n n +1 +1 可根据归纳法证明。可根据归纳法证明。 对于两种特殊形式

19、的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉树满二叉树和完全二叉树），还），还 特别具备以下特别具备以下2 2个性质：个性质： 27 完全二叉树：完全二叉树：深度为深度为k 的的、有有n个结点个结点 的二叉树，当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与 深度为深度为k 的满二叉树中编号从的满二叉树中编号从1至至n的结的结 点一一对应。点一一对应。 A O B C GE K D J F IHNML 深度为深度为4 4的满二叉树的满二叉树 完全二叉树完全二叉树 A B C GE I D H F J 为何要研究为何要研究 这两种特殊这两种特殊 形式？形式？ 满二叉树：满二叉树：一棵深度为一棵深度为k 且有且有2k -1个结点的二叉树。个结点的二叉树。 （特点：每层都（特点：每层都“充满充满”了结点）了结点） 刘解释：完全二叉树的特点是只有最后一层叶子不满，刘解释：完全二叉树的特点是只有最