结点
和链表类似,树存储结构中也将存储的各个元素称为
"
结点
"
。
对于树中某些特殊位置的结点,还可以进行更细致的划分,比如:
父结点(双亲结点)、孩子结点和兄弟结点:
树根结点(简称
"
根结点
"
):特指树中没有双亲(父亲)的结点,一棵树有且仅有一个根结点。
叶子结点(简称
"
叶结点
"
):特指树中没有孩子的结点,一棵树可以有多个叶子结点。
子树
通常,我们将一棵树中几个结点构成的
“
小树
”
称为这棵树的
“
子树
”
。
知道了子树的概念后,树也可以这样定义:树是由根结点和若干棵子树构成的。
注意:单个结点也可以看作是一棵树,该结点即为根结点。
结点的度
一个结点拥有子树的个数,就称为该结点的度(
Degree
)。
比较一棵树中所有结点的度,最大的度即为整棵树的度。
结点的层次
从一棵树的树根开始,树根所在层为第一层,根的孩子结点所在的层为第二层,依次类推。