第11讲树和二叉树A课件.ppt

1、1第第1010讲讲 树和二叉树树和二叉树 教学内容：教学内容：6.1 6.1 树的基本概念和基本术语；树的基本概念和基本术语；（P118-P120P118-P120）6.2 6.2 二叉树。二叉树。(P121-127)(P121-127)教学目的：教学目的：了解树的基本概念和基本术语，了解树的基本概念和基本术语，理抽二叉树的定义；理抽二叉树的定义；理解二叉树的性质。理解二叉树的性质。教学重点：教学重点：树和二叉树的定义；树和二叉树的定义；二叉树的性质及其证明二叉树的性质及其证明.教学难点：教学难点：二叉树的性质及其证明二叉树的性质及其证明26.1 树的基本概念1.树的定义树的定义2.若干术语若

2、干术语3.逻辑结构逻辑结构4.存储结构存储结构5.树的运算树的运算31.树的定义树的定义注注1：过去许多书籍中都定义树为过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是树树”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具有树的定义具有递归性递归性，即树中还有树。，即树中还有树。由一个或多个由一个或多个(n0n0)结点组成的有限集合结点组成的有限集合T T，有，有且仅有且仅有一个结点称为根一个结点称为根（rootroot），），当当n1n1时，其余的时，其余的结点分为结点分为m(m0)m(m0)个个互不相交互不相交的有限集合的有限集合T1,T2T1,

3、T2，TmTm。每个集合本身又是棵树，被称作这个根的。每个集合本身又是棵树，被称作这个根的子树子树 。4树的表示法有几种：树的表示法有几种：图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法左孩子右兄弟表示法左孩子右兄弟表示法这些表示法的示意图这些表示法的示意图参见教材参见教材P120P120树的抽象数据类型定义树的抽象数据类型定义参参见教材见教材P118-119P118-1195图形表示法：图形表示法：教师教师学生学生其他人员其他人员9999级级20002000级级 20012001级级20022002级级湖南文理学院湖南文理学院计算机系计算机系电气

4、系电气系物理系物理系叶子叶子根根子树子树6广义表表示法广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)根作为根作为由子树森林组成的由子树森林组成的表的名字写在表的左边表的名字写在表的左边datalink 1 link 2.link n麻烦问题：应当开设多少个链域麻烦问题：应当开设多少个链域?7左孩子右兄弟表示法左孩子右兄弟表示法数据数据左孩子左孩子 右兄弟右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)8 树的抽象数据类型定义树的抽象数据类型定义（见教材（见教材P118-119P118-119）ADT Tree数据对象数据对象D:数据关系数据关系R

5、:基本操作基本操作 P：ADT Tree若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有15个个92.若干术语若干术语即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同

6、层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一

7、）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。102.若干术语（续）若干术语（续）即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数（有几个直接后继就是几度（有几个直接后继就是几度，亦称，亦称“次数次数”）结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的

8、最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（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节节）15定义：定义：是是n（n0）个结点的有限集合，由一个根结点以及两）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为棵互不相交的、分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成。逻辑结构：逻辑结构：一对二（一对二（1：2）基本特征基本特征:每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）；左子树和右子树次序不能颠倒（有序树）。左子树和右子树次序不能颠倒（有序树）。基本形态：基本形态：5种种/2种种16二叉树的抽象数据类型定义二叉树的抽象数据

13、类型定义（见教材（见教材P P121-122121-122）ADT BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则，则R=；若若D，则，则R=H；存在二元关系：；存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明 /关于左子树和右子树的说明关于左子树和右子树的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有20个个17讨论讨论1 1：第：第i i层的结点数至多是多少？层的结点数至多

14、是多少？（利用二进制性质可轻松求出）（利用二进制性质可轻松求出）性质性质1:1:在二叉树的第在二叉树的第i i层上至多有层上至多有个结点（个结点（i0i0）。）。性质性质2:2:深度为深度为k k的二叉树至多有的二叉树至多有个结点（个结点（k0k0）。）。2 2i-1i-1个个提问：第提问：第i i层上至少有层上至少有 个结点？个结点？1 1讨论讨论2 2：深度为：深度为k k的二叉树，至多有多少个结点？的二叉树，至多有多少个结点？（利用二进制性质可轻松求出）（利用二进制性质可轻松求出）2 2k k-1-1提问：深度为提问：深度为k k时至少有时至少有 个结点？个结点？k k18讨论讨论3 3

15、：二叉树的叶子数和度为：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？性质性质3:3:对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个，则叶子数（则叶子数（n n0 0）必定为必定为n n2 21 1（即（即n0=n2+1）二叉树中全部结点数二叉树中全部结点数nn0+n1+n2(叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数)二叉树中全部结点数二叉树中全部结点数nB+1 (总分支数根结点总分支数根结点 )（除根结点外，每个结点必有一个直接前趋，即一个分支）（除根结点外，每个结点必有一个直接前趋，即一个分支）总分支数总

16、分支数B=n1+2n2 (1(1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个)n0+n1+n2=n1+2n2+1,即即n0=n2+1实际意义：实际意义：叶子数叶子数2 2度结点数度结点数1 1ABCGEIDHFJ19对于两种特殊形式的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉树满二叉树和完全二叉树），），还特别具备以下还特别具备以下2 2个性质：个性质：性质性质4:4:具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为 loglog2 2n n 1 1性质性质5:5:对完全二叉树，若从上至下、从左至右编号，对完全二叉树，若

17、从上至下、从左至右编号，则编号为则编号为i 的结点，其左孩子编号必为的结点，其左孩子编号必为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

18、-1 -1 或或2 2k-1k-1n n 2 2k k三边同时取对数，于是有：三边同时取对数，于是有：k-1logk-1log2 2nk nk 因为因为k k是整数，所以是整数，所以k=k=loglog2 2n n +1+1可根据归纳法证明。可根据归纳法证明。20满二叉树：满二叉树：一棵深度为一棵深度为k 且有且有2k-1个结点的二叉树。个结点的二叉树。（特点：每层都（特点：每层都“充满充满”了结点）了结点）完全二叉树：完全二叉树：深度为深度为k 的的，有有n个结点个结点的二叉树，当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与深度为深度为k 的满二叉树中编号从的满二叉树中编号从1至

19、至n的结的结点一一对应。点一一对应。AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树深度为深度为4 4的的完全二叉树完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原！因为它们在顺序存储方式下可以复原！刘解释：完全二叉树的特点就是，只有最刘解释：完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。后一层叶子不满，且全部集中在左边。这其实是这其实是的含义。在的含义。在的的“完全二叉树完全二叉树”是指是指n1=0的情况。的情况。213.3.深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点

20、。)9 9 )8 8 )9 91 12.2.深度为深度为k 的二叉树的结点总数，最多为的二叉树的结点总数，最多为 个。个。)k-1k-1 )log)log2 2k k )k k )k k课堂练习：课堂练习：1.1.树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。)高度高度 )层次层次 )深度深度 )度度课堂讨论：课堂讨论：二叉树是不是树的特殊情况？二叉树是不是树的特殊情况？答：答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树，不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树，并非一般树的特例。并非一般树的特例。它的子树有顺序规定它的子树有顺序规定，分

21、为左子树和右子树。不能随，分为左子树和右子树。不能随意颠倒。意颠倒。：满二叉树和完全二叉树有什么区别？：满二叉树和完全二叉树有什么区别？答：答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1n-1层是满的，层是满的，但最底层却允许在右边缺少连续若干个结点。但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一满二叉树是完全二叉树的一个特例。个特例。224.4.二叉树的存储结构二叉树的存储结构一、顺序存储结构一、顺序存储结构按二叉树的结点按二叉树的结点“自上而自上而下、从左至右下、从左至右”编号，用编号，用一组连续的存储单元存储。

22、一组连续的存储单元存储。123456789问：顺序存储后能否复原成唯一对应的二叉树形状？问：顺序存储后能否复原成唯一对应的二叉树形状？答：答：若是完全若是完全/满二叉树则可以做到唯一复原。满二叉树则可以做到唯一复原。而且有规律：下标值为而且有规律：下标值为i i的双亲，其左孩子的下标值必为的双亲，其左孩子的下标值必为2i2i，其右孩子的下标值必为，其右孩子的下标值必为2i2i1 1（即性质（即性质5 5）例如，对应例如，对应22的两个孩子必为的两个孩子必为44和和5,5,即即B B的左孩子必的左孩子必是是D,D,右孩子必为右孩子必为E E。T0T0一一般不用般不用23讨论：讨论：不是完全二叉树

23、怎么办？不是完全二叉树怎么办？答：答：一律转为完全二叉树！一律转为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点虚结点”，其内容为空。，其内容为空。123456789.16ABECD缺点：浪费空间；插入、删除不便缺点：浪费空间；插入、删除不便 24二、链式存储结构二、链式存储结构用二叉链表即可方便表示。用二叉链表即可方便表示。二叉树结点数据类型定义：二叉树结点数据类型定义：typedef struct node*tree_pointer;typedef struct node int data;tree_pointer left_child,right_child;node;一般从根结点开始存储。一般从根结点开始存储。（相应地，访问树中结点时（相应地，访问树中结点时也只能从根开始）也只能从根开始）注：注：如果需要倒查某结点的如果需要倒查某结点的双亲，可以再增加一个双亲双亲，可以再增加一个双亲域（直接前趋）指针，将二域（直接前趋）指针，将二叉链表变成三叉链表。叉链表变成三叉链表。25例：例：ABECD