第6章 树

6.2 二 叉 树
在有序树中有一种特殊的树，称为二叉树。 6.2.1 二叉树的定义与性质 1. 二叉树的定义 二叉树(Binary Tree)是有限的数据类型相同结点的集
合。 (1) 这个集合或者是空，称为空二叉树； (2) 或者有且仅有一个根结点； (3) 树中每个结点最多只有两个子树(即树的度小于等 于2)，并且子树有左右之分，次序不能互换； (4) 二叉树是一种递归的数据结构。
第6章
树
树形结构是十分重要的非线性结构，结点之间是一对 多的关系。也就是说一个结点如果有直接前驱结点，则只能 有一个直接前驱结点，但是可以有多个直接后继结点。
6.1 树
6.1.1 树的定义 图6.1是一个软件公司的组织架构图，假设有且仅有总 经理，总经理下面有若干个部门经理，每个部门经理下面又 有若干个项目经理，每个项目经理下面又有若干名程序员， 它是一种典型的树形结构。
6.1 树
树的深度(高度)：树中结点的最大层数。 图6.2中树的最大层数是4，所以树的深度是4。 堂兄弟结点：双亲在同一层的结点。 图6.2中G和H是堂兄弟结点；E和F是兄弟结点。 有序树和无序树：树中各结点的子树按照从左到右的 次序是不可交换的，该树称为有序树。反之称为无序树。 森林：m(m≥0)个互不相交的树的集合。在数据结构中 ，只要删除一棵树的根结点就成了森林。
右子树 左子树
左子树
(e)
右子树
(e)
右子树
(d) 左子树为空的二叉树 图6.4 二叉树的五种形态
(e) 左、右子树均非空的二叉树
6.2 二 叉 树
3. 树与二叉树的区别 尽管树与二叉树有很多相似之处，但它们是两种不同 的数据结构。二叉树中每个结点的子树要区分左子树和右子 树，即使在结点只有一棵子树的情况下也要明确指出该树是 左子树还是右子树。例如图6.5是两棵不同的二叉树，是两 棵有序树。而图6.6是一棵普通无序树。如果将图6.5中的两 棵二叉树看成普通的无序树时，那么这三棵树是一样的。
6.1 树
6.1.3 树的表示形式 1. 树的直观表示法 树的直观表示法就是以倒着的分支树的形式表示，图 6.2就是一棵树的直观表示。其特点就是对树的逻辑结构的 描述非常直观。它是数据结构中最常用的树的描述方法。 2. 树的二元组表示法 图6.2的树用二元组表示应为 D={A, B, C, D, E, F, G, H, I, J, K, L, M, N} R={<A,B>, <A,C >, <A,D>, <B,E>, <B,F>, <B,G>, <C,H>, <D,I>, <D,J>, <H,K>, <H,L>, <H,M>, <H,N>}
6.1 树
2. 基本操作集合 (1) InitTree(&T)：树的初始化操作。将T初始化为一棵空
树。 (2) (3) (4) (5) (6) (7) (8) CreateTree(&T)：创建树T。 DestroyTree(&T)：销毁树T。 TreeEmpty(T)：判断树是否为空。 Root(T)：返回树的根操作。 Parent(T,e)：返回结点的双亲操作。 FirstChild(T,e)：返回结点e的第一个孩子结点。 NextSibling(T,e)：返回结点e的下一个兄弟结点。
6.1 树
图6.2是一棵树的结构示意图。
层次 A B E F G C H I D J 1 2
3
K
L
M
N
4
6.1 树
在图6.2中，有如下特点： (1) 该树是由14个数据类型相同的结点组成的，是一 棵非空树； (2) 有且仅有一个根结点为A； (3) 根结点A有3棵子树，3棵子树的根结点分别是B、 C、D； (4) 3棵子树互不相交，每棵子树又是一棵树。
6.2 二 叉 树
4. 满二叉树和完全二叉树 (1) 满二叉树 在一棵二叉树中，若所有的分支结点都有左孩子和右 孩子，并且所有叶子结点的层数等于树的深度，这样的二叉 树称为满二叉树，如图6.7(a)所示。 (2) 完全二叉树 在一棵二叉树中，除了最后一层外，其余各层都是满 的，而最后一层或者是满的，或者从最右边开始缺少若干个 连续结点，这样的二叉树称为完全二叉树，如图6.7(b)所示 。 完全二叉树的叶子结点只能出现在最大的两层上。若 完全二叉树的分支结点没有左孩子结点，则它一定没有右孩 子结点。
6.1 树
3. 树的其他表示法 (1) 嵌套集合表示法：集合的集合，其中任意两个集合 ，或者不相交，或者一个包含另一个。每个圆圈表示一个集 合，套起来的圆圈表示包含关系,如图6.3(a)所示。 (2) 凹入法：用不同长度的线段表示各结点，根结点长 度最长，而线段的凹入程度体现了各结点之间的包含关系， 如图6.3(b)所示。 (3) 广义表表示法：使用小括号将集合层次和包含关系 表示出来。图6.2的广义表表示法为A ( B ( E , F , G ) , C ( H ( K , L , M , N ) ) , D ( I , J ) )。
6.2 二 叉 树
完全二叉树的编号方法和满二叉树相同。满二叉树一 定是完全二叉树，而反之不然。
6.2 二 叉 树
5. 二叉树的性质 性质1 一棵非空二叉树的第i层上最多有2i-1个结点 (i≥1)。 证明：用数学归纳法。 当i=1时，非空的二叉树只有一个根结点，21-1=1，结 论成立。 假设i=n-1层时，结论成立，则第n-1层上最多有2n-11=2n-2个结点。 当i=n时，根据二叉树的定义，每个结点最多有两个子 结点(左孩子和右孩子结点)，因为第n-1层上最多有2n-2个 结点，所以第i层上最多有2×2n-2=2n-1个结点。 综上所述，结论成立。
6.1 树
路径、边和路径长度：对于任意两个结点am和an，如 果树中存在一个结点序列am…an,使得ai是ai+1(m≤i≤n)的 双亲结点，则称am和an之间存在一条路径。 图6.2中A和N之间存在一条路径，该路径可以表示为 ACHN，路径长度等于3。F和H之间不存在路径，因为F和H 之间需经过根结点才能相连。
A B E F
A B E F G K C H L M
D
D I J
C
G H K L M N I J
N
6.1 树
6.1.4 树的抽象数据类型
1. 数据对象集合 树的数据对象集合为树的各个结点的集合。一个数据 元素可能有m(m≥0)个后继元素，但只有一个前驱元素。元 素之间是一对多的关系。例如，在树(A(B(E(K,L),F), C(G(M),H,I(N)),D(J)))中，“K”和“L”是结点“E”的后继结 点，结点’E’是’K’和’L’的前驱结点。
6.1 树
6.1.2 树的基本术语 结点：树的结点包含一个数据和若干个指向其子树的 分支。 结点的度：每个结点所拥有的子树的个数。 图6.2中A的度是3；H的度是4；M没有子树，度为0。 树的度：树中各结点度的最大值。 图6.2中H的度是4，是树中各结点度的最大值，所以树 的度是4。
叶子结点(终端结点)：度为0的结点。 图6.2中E、F、G、K、L、M、N、I、J的度都是0，所 以该树中共有9个叶子结点。 分支结点(非终端结点)：度不为0的结点。度为1的结点 称为单分支结点；度为2的结点称为双分支结点。 图6.2中C是单分支结点；D是双分支结点。 孩子结点、双亲结点和兄弟结点：树中每个结点的子 树的根称为该结点的孩子结点。该结点称为孩子的双亲结点 。具有同一双亲的孩子结点称为兄弟结点。
6.2 二 叉 树
性质2 深度为k的二叉树最多有2k-1个结点(k≥1)。 证明：当深度为k的二叉树上每一层所拥有的结点数达 到最大时，该二叉树所拥有的结点个数最多。由性质1可知 ，第i(1≤i≤k)层上最多拥有2i-1个结点，则整个二叉树所拥 有的结点个数S为 根据性质2可知，深度为k的满二叉树上有个结点。如 图6.7(a)所示，深度为4的满二叉树，树的结点个数为=15个 结点。
ቤተ መጻሕፍቲ ባይዱ
6.2 二 叉 树
性质3 任何一棵二叉树，如果其叶子结点的个数为n0，度为 2的双分支结点个数为n2，则有n0= n2+1。 证明：假设一棵二叉树T所拥有的总结点个数为n，叶子结点 个数为n0，单分支结点个数为n1，双分支结点个数为n2，则二叉 树所拥有的结点总数为 n=n0+n1+n2 (6-1) 假设二叉树T中所拥有边的条数为B。 除了根结点外，每个结点都会有一条连接双亲结点的边，所 以： B=n-1 (6-2) 由于单分支和双分支结点有连接孩子结点的边，所以： B=n1+2n2 (6-3) 由公式6-2和6-3可以得出： n=n1+2n2+1 (6-4) 由公式6-1和6-4可以得出： n0=n2+1 (6-5
6.1 树
(2) 凹入法：用不同长度的线段表示各结点，根结点长 度最长，而线段的凹入程度体现了各结点之间的包含关系， 如图6.3(b)所示。 (3) 广义表表示法：使用小括号将集合层次和包含关系 表示出来。图6.2的广义表表示法为A ( B ( E , F , G ) , C ( H ( K , L , M , N ) ) , D ( I , J ) )。
6.2 二 叉 树
log 性质4 具有n(n≥0)个结点的完全二叉树的深度k为 或 (n 1)
2
。
log2 n 1
证明：假设完全二叉树的深度为k，根据性质2和完全 二叉树定义可知，它的前k-1层一定是满的，即前k-1层共有 个结点，而前k层最多有个结点，因此可以得到不等式： 可以转化为 2 n 1≤ 2 取对数后得k 1 log (n 1) ≤ k即 log (n 1) ≤ k log (n 1) 1 因为k只能取整数，所以 k= log (n 1)。 因为完全二叉树的深度为k，前k-1层有个结点，第k层 上最少有一个结点，所以。又因为前k层上最多有个结点， 所以。 可得不等式 取对数后得 即 因为k只能取整数，所以 k=。