精品文档
§ 7.1 树的概念
【定义】 树(Tree )是n (n>0)个结点的有限集合 T,它满足如下两个条件:
(1) 有且仅有一个特定的称为根( Tree )。
Root )的结点；
(2) 其余的结点可分为 m( m> 0)个互不相交的有限集合，其中每一个集合又都是一颗树, 并称为根的子树(Sub
【基本术语】k
1. 树的结点包含一个数据元素及若干指向其子树的分支。
结点拥有的子树数称为 结点的度(degree )。
如图7.1 , A的度为3, C的度为1, F的度为0。
图
7.1.1
2. 度为0的结点称为叶子(leaf )或终端结点。例如K、L、F、G Ml、J。 度不为0的结点称为分支结点或非终端结点。
除根结点外，分支结点也称为内部结点。
3. 3。
4.结点的子树的根称为该结点的
树的度是树内各结点的度的最大值，如图 7.1中树的度为
孩子(Child )，该结点称为孩子的 双亲(pare nt )。
如图7.1.1 , B为A的子树的根，则 B是A的孩子，而 A则是B的双亲。 同一个双亲的孩子之间互称为 兄弟(sibli ng ),例如B、C、D互为兄弟。 将这些关系进一步推广，可认为 所有结点。例如，M的祖先为A D H。 反之，结点的子树中的任一结点都称为该结点的
子孙，女口 B的为E、F、K L。
D是M的祖父。结点的 祖先是从根到该结点所经分支上的
5. 结点的层次(level )是从根开始定义起，根为第一层，根的孩子为第二层。 若某结点在第x层，则其子树的根就在 x+1层。
树中结点的最大层次称为树的
高度或深度(depth )。如图7.1的树的深度为 4。
6. 如果将树中的结点的各子树看成从左到右是有次序的(即不能互换)
则称为无序树。如图7.1.2。
，则称该树为 有序树，否
图7.1.2
两棵不同的有序树
7. 森林(forest )是m( m>0)棵互不相交的树的集合。
37欢迎下载
精品文档
§ 7.2 二叉树
§ 7.2.1 二叉树的定义
二叉树（binary tree ）是一种树型结构，它的每个结点 至多只有二棵子树（即二叉树中不存在度大于
二叉树的子树有左右之分，其次序不能任意颠倒。
（如图 7.2.1）
图 7.2.1
满二叉树和完全二叉树是两种特殊形态的二叉树。 满二叉树是指深度为k,且有2k-1个结点的二叉树。
完全二叉树 是指深度为k，有n个结点，当且仅当每一个结点都与深度为 编号从1到n的结点 ------- 对应时。
2结点），并且，
k的满二叉树中
图7.2.2 满二叉树 § 7.2.2 二叉树的性质 性质1:在二叉树的第i层上至多有 性质2:深度为k的二叉树至多有 性质3:对任意一棵二叉树，如果度为 性质4 :具有n个结点的完全二叉树的深度为
图7.2.3 完全二叉树 图7.2.4 非完全二叉树
①个结点（i > 1 ）。 ②个结点（k> 1 ）。
2的结点数为n2,则其叶子结点数为
③。
log 2n 1
，则对任一
性质5:如果对一棵有n个结点的完全■二叉树.的结点按层序编号（每层从左到右） 结点i （ K i w n）,有：
① 如果i=1，则结点i是二叉树的根；如果i>1，则其双亲结点是i div 2 ② 如果2*i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子为 2*i ③ 为
i-1
如果2*i+1>n，则结点i无右孩子，否则其右孩子2*i+1 ［参考答案及证明］:
证明：利用归纳法
当i=1时，只有一个根结点，显然， 2i-1=20=1正确； 假设对所有的j , 1 w j
由假设，第i-1层上至多有2i-1个结点，由于二叉树中的每个结点的度至多为 第i层上的最大结点数为第i-1层上最大结点数的2倍，即2*2i-2 =2i-1
2,故在
38欢迎下载
精品文档
② 2 k-1
证明：深度为K的二叉树的最大结点数为
k
k
（第i层上的最大结点数）
i 1
i 1
21 1 2k 1
③ n 2+1
证明：设叶子结点数为 n0,度为1的结点数为n1,则该数结点的总数为：
n = no + n1 + n2 （1）
树中结点之间的连线称为分支。树中除根结点外，其余每个结点都有一个分支进入， 设B为二叉树分支的总数，则有：
B = n - 1
另一方面，这些分支是由度为
1或2的结点射出的，所以：
B = n 1 + 2n 2
（2）
所以： n - 1 = n 1 + 2n 2 由式（1 ）和（2）得：
no + n1 + n2 - 1
即卩：no = n2 + 1
④
=n1 + 2n?
证明：假设深度为 K的完全二叉树的结点数为 n,则根据性质2和完全二叉树定义有:
2
k 1
1 n 2
k
1 或 2 n 2
k 1 k
于是
k 1 log 2 n k
T k 是整数??? k log 2 n 1
④ 证明略
§ 7.2.2 二叉树的存储结构
1 ?顺序存储结构
将二叉树的所有结点按一定的次序，存储到一片连续的存储单元中。这种结构，较适
用于满二叉树或近似满二叉树。
39欢迎下载
精品文档
如图7.2.5中完全二叉树的存储结构如下:
A B C D E F G H I J K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
40欢迎下载
图 7.2.5
精品文档
图7.2.6中的二叉树的存储结构如下:
B C D 1 2 3 4 F G 5 6 7 I M 8 9 10 11 12 13 14 15 图726
可以看出，当二叉树较稀疏时，采用顺序存储将造成浪费。
［练习］
1）如果完全二叉树最多有
n层，那么存储该树的数组最少设
__________ 个单元;
2）某结点存储于 S［i］，则存在双亲结点的条件：
其双亲结点位于 S［ ____ ］，其左孩子结点位于
if _____________________ S［ ___ ］；
2 ?链式存储结构
设计不同的结点结构可以构成不同形式的链式存储结构。
由二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左右子树的两个分支 构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左、右指针域，如图 有时为了便于找到结点的双亲，
则还可以在结点的结构中增加一个指向其双亲结点的指针域。
7.2.7。
用这两种结点结构所得的二叉树的存储结构分别称为二叉链表和三叉链表，如图
7.2.8。
图 7.2.8
Lchild Data 图 7.2.7
Rchild 在具体应用中采用什么存储结构，除根据二叉树的形态之外，还应考虑需进行何种操作。如 找结点的双亲，在三叉链表中容易实现，而在二叉链表中则需从根中指针出发巡查。
41欢迎下载
高中信息技术-竞赛班数据结构专项培训教程-07树教案
