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

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

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

结点的度：结点所拥有子树的个数，图中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

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

6

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

二叉树的性质： 性质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个节点。

二叉树的性质： 性质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个节点。

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

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

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

13

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

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

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

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

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

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

例题：下表是根据完全二叉树的特性用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次从小到大，同一层从左到右顺序存储，#表示空节点，@表示存储数据结束）。要求画出对应存储结构的二叉树。 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 @

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

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

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

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

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

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

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

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

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