第三节 树与二叉树 树的基本概念： 前面我们讨论的线性表，栈、队列和数组等都是线性结构。而树是一种非线性数据结构，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起，清晰地反映了数据元素之间的层次关系。

Presentation on theme: "第三节 树与二叉树 树的基本概念： 前面我们讨论的线性表，栈、队列和数组等都是线性结构。而树是一种非线性数据结构，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起，清晰地反映了数据元素之间的层次关系。"— Presentation transcript:

1 第三节 树与二叉树 树的基本概念： 前面我们讨论的线性表，栈、队列和数组等都是线性结构。而树是一种非线性数据结构，它的每一个结点，都可以有不止一个直接后继，除根外的所有结点，都有且只有一个直接前趋。这些数据结点按分支关系组织起，清晰地反映了数据元素之间的层次关系。

2 算 法 与 数 据 结 构 现实世界中，能用树的结构表示的例子： 学校的行政关系（P31）、书的层次结构（P32）、人类的家族血缘关系等。

3 例：下图是一个有13个结点的树，其中A是根，其余结点为分三个互不相交的子集： T1＝{B,E,F,K,L} T2＝{F,G}
T3＝{D,H,I,J,M} T1、T2和T3都是根A的子树。 3

4 结点的度：结点所拥有子树的个数，图中A的度为3，C的度为1，F的度为0。
树结构的基本术语： 结点的度：结点所拥有子树的个数，图中A的度为3，C的度为1，F的度为0。 叶子结点：树中度为0的结点，图中的K、L、F、G、M、I、J均称为叶子结点（或终端结点）。 子结点与父结点：把每一个结点的一个或多个后件称为该点的子结点；反之，这个结点称为其子结点的父结点，同一个父结点的子结点之间互称为兄弟。 树的度：树中各结点的度的最大值，度不为0的结点为非终端结点同，又叫分支结点。 树的深度：树中结点的最大层次称为树的深度或高度。图中树的深度为4。 森林：N>0或N=0棵互不相交的树的集合组成森林。图中将根结点A去掉，其中三棵子树就组成一个森林。 4

5 二叉树（Binary Tree）： 因为树的每个结点的度不同，存储困难，使得对树的处理算法很复杂。所以引出二叉树的讨论。
二叉树是一种很有用的非线性结构。 二叉树具有以下两个特点： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 5

6 6

7 二叉树的性质： 性质1：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
例子1：某二叉树中度为2的结点有18个，则该二叉树中有 个叶子结点。 特别要注意：二叉树不是树的特殊情况。 a a b b 两棵不同的二叉树 7

8 二叉树的性质： 性质2：二叉树的第i层上至多有2 i-1（i 1）个结点 第一层(i=1)，有21-1=1个节点。
4 2 3 1 6 7 8 9 10 11 12 13 14 15 5 第一层(i=1)，有21-1=1个节点。 第二层(i=2)，有22-1=2个节点。 第三层(i=3)，有23-1=4个节点。 第四层(i=4)，有24-1=8个节点。

9 二叉树的性质： 性质3：深度为h的二叉树中至多含有2h-1个结点 1+2+4+…+2m-1=2m-1(等比数列前M项和)
6 7 8 9 10 11 12 13 14 15 5 1+2+4+…+2m-1=2m-1(等比数列前M项和) 此树的深度h=4，共有24-1=15个节点。

10 满二叉树与完全二叉树 算 法 与 数 据 结 构 满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。
完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 注意：满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 若一棵完全二叉树的结点数n为偶数，则叶子结点数为结点数除以2（即：n/2），若结点数为奇数，则 叶子结点数为结点数加一再除以2（即：（n+1）/2）

11 满二叉树的特点： 每一层上都含有最大结点数。 11

12 完全二叉树的特点：除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置
完全二叉树的特点：除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置 12

13 13

14 真题讲解： 一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：（2009年第十五届 单选） A) nk B) nk-1 C) (k+1)n-1 D. (k-1)n+1 完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。（2008年第十四届 单选） A. N B. 2*N C. N D. 2N E. N/2

15 规律总结： 对于完全二叉树而言 算 法 与 数 据 结 构 如果它的结点个数为偶数，则该二叉树中：叶子结点的个数=非叶子结点的个数
如果它的结点个数为奇数，则该二叉树中：叶子结点的个数=非叶子结点的个数+1 （即叶子结点数比非叶子结点数多一个） 1 2 3 4 1 2 3 4 5 2 叶子结点 2 非叶子结点 2

16 树的存储结构 分为两种： 顺序存储结构： 对树中的结点进行编号，利用下标变量存放结点的数据，将一棵树的所有结点数据存储到一维数组中。
链式存储结构： 利用多重链表保存树中的各个结点的数据及其所有子树的信息。

17 二叉树的存储结构 顺序存储结构 首先对二叉树中的结点从根开始按照从上至下、从左至右的顺序逐层编号，用结点的编号作为下标，将所有结点一次存放在一维数组中。 b e d a c f g 1 2 3 4 5 6 7

18 a c b g 用结点的编号i作为下标，构成记录数组T，变量T[i]存放二叉树的第i个结点的数据。 e f d 从图上可以看出：
1 2 3 4 5 6 7 从图上可以看出： 结点i的左子树一定保存在结点2i数据单元中；右子树一定保存在结点2i+1数据单元中； 真题讲解： （2010年第十六届奥赛 单选） 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（   ）号位置 A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2

19 a c b e f i 满二叉树和完全二叉树一般应用顺序存储结构进行数据的存储。
对于非满二叉树，会有某些编号没有对应的结点（通常称为“虚结点”），通常可以用特殊标记符号（例如：#）表示虚结点，将树转换为满二叉树进行存储。 b e d a c f g h i j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g # h i j

20 例题：下表是根据完全二叉树的特性用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次从小到大，同一层从左到右顺序存储，#表示空节点，@表示存储数据结束）。要求画出对应存储结构的二叉树。
b a c d e h f g 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c # d e f g h @

21 b a c d e f 2.链式存储结构 对于二叉树的每个结点需要保存三种信息：数据元素、左子树、右子树，故可以增设两个分别指向左、右子树结点的指针来表达树的结构。因此，在二叉树对应的二重链表中，每个结点包含三个域：数据域、左指针、右指针。 这种链表称为二叉链表。二叉链表的表头指针bt指向根结点。 a b c d e 左指针域 数据域 右指针域 lchild data rchild f

22 二叉树的遍历 二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结构定义得知，二叉树是由"根结点"、"左子树"和"右子树"三部分构成，则遍历二叉树的操作可分解为"访问根结点"、"遍历左子树"和"遍历右子树"三个子操作，并且由二叉树的定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样"递归"进行。 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 若二叉树为空，则空 操作；否则 (1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树。 操作；否则 (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。 操作；否则 (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。

23 二叉树的遍历 前序遍历：ABDEGHCFIJ 中序遍历：DBGEHACIJF 后序遍历：DGHEBJIFCA

24 例题：设一棵二叉树的中序遍历dbgeachfi，后序遍历为dgebhifca，画出这棵二叉树，并写出它的前序遍历。
前序遍历：abdegcfhi

25 3、设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF，则后序遍历结果为： DEBFCA
3、已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为（ B ） A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG 3.具有3个结点的二叉树有（ D ） A) 2种形态 B) 4种形态 C) 7种形态 D) 5种形态 4. 设有下列二叉树：对此二叉 树前序遍历的结果为（ B ） A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT

26 真题讲解： 一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（   ）。（2010年第十六届 多选） A．0      B. 2         C. 4         D. 6 二叉树T，已知其先根遍历是 （数字为结点的编号，以下同），后根遍历是 ，则该二叉树的可能的中根遍历是（ ）。 （2008年第十四届 不定项选择） A B C D

27 + / * x b - 例题：如图所示的二叉树，写出它的中序遍历、前序遍历和后序遍历。 ^ 5 2 3
前序遍历：+*5x3-/b^x2，运算符 号放在参与运算的变量及数字的 前面，这种方式称为前缀表示。 中序遍历：5*x-3+b/x^2，运算符 号放在参与运算的变量及数字的 中间，这种方式称为中缀表示。 这种方式同人们熟知的代数式类似。 - 后序遍历：5-3x*bx2^/+，运算符 号放在参与运算的变量及数字 的后面，这种方式称为后缀表示。

28 + * 例题：将表达式A+B*C/D写成前缀表示与 后缀表示。 二叉树的前序遍历就是表达 式的前缀表示：+A*B/CD
注意：在根据已知的表达式画出对应的二叉树时，应考虑在前 缀表示与后缀表示中保持表达式中运算符号的优先级不改变。 二叉树的前序遍历就是表达 式的前缀表示：+A*B/CD A + * B / C D 二叉树的后序遍历就是表达 式的后缀表示：ABCD/*+

29 真题讲解： 前缀表达式“+ 3 * 2 + 5   12 ” 的值是（ ）。（2010年第十六届 单选） A B C D. 65 表达式a*(b+c)-d的后缀表达式是： （2009年第十五届 单选） A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd