![](https://csdnimg.cn/release/download_crawler_static/87771203/bg6.jpg)
图 1-1 树的层次结构
由图 1-1 可以看出树的形状就像一棵现实中的树,只不过是倒过来的.
1.1.2
树的相关术语
结点的度
[1]
:一个结点的儿子结点的个数称为该结点的度.一棵树的度是指该树中结
点的最大度数.
叶结点:树中度为零的结点称为叶结点或终端结点.
分枝结点:树中度不为零的结点称为分枝结点或非终端结点.
部结点
[1]
:除根结点外的分枝结点统称为部结点.例如在图 1-1 中,结点,
A, B
和
E
的度分别为 3,2,0.其中
A
为根结点,
B
为部结点,
E
为叶结点,树的度为 3.
路径:如果存在树中的一个结点序列
K
1
, K
2
,L , K
j
,使得结点
K
i
是结点
K
i1
的父结点
1 i j
,则称该结点序列是树中从结点
K
i
到结点 K
j
的一条路径或道路 .我们称这条
路径的长度为
j 1
,它是该路径所经过的边 (即连接两个结点的线段 )的数目.树中任一
结点有一条到其自身的长度为零的路径.例如,在图 1-1 中,结点
A
到结点
I
有一条路径
ABFI
,它的长度为 3.
祖先:如果在树中存在一条从结点
K
到结点
M
的路径,则称结点
K
是结点
M
的先,
也称结点
M
是结点
K
的子或后裔.例如在图 1-1 中,结点
F
的祖先有
A, B
和
F
自己,而
它的子包括它自己和
I , J
.注意,任一结点既是它自己的祖先也是它自己的子.
真祖先、真子:我们将树中一个结点的非自身祖先和子分别称为该结点的真祖
先和真子.在一棵树中,树根是唯一没有真祖先的结点 .叶结点是那些没有真子的结点 .
子树是树中某一结点及其所有真子组成的一棵树.
结点高度
[1]
:树中一个结点的高度是指从该结点到作为它的子的各叶结点的最长
路径的长度.树的高度是指根结点的高度 .例如图 1-1 中的结点
B
,
C
和
D
的高度分别
2,0 和 1,而树的高度与结点
A
的高度相同为 3.
结点的深度或层数:从树根到任一结点
n
有唯一的一条路径,我们称这条路径的长