树的家族系列之一——树的基本知识

树的家族系列之一——树的基本知识

    树是非常常用的非线性数据结构，分为有序树和无序树，有序树是指树的分支具有不可对换性，即树通过左右旋转或者分支位置互换之后和原树不一样，这种树通常是有序的。与此相对的是无序树，即同一个根节点下的所有分支的位置可以互换，互换之后树保持不变。

    树是n(n≥0)个结点的有限集。若 n = 0，称为空树，即空树也是树。
    任意一颗非空的树中，特点如下：

[1] 有且仅有一个特定的结点称为树根或根节点
[2] 任意一个节点的分支（子树）不存在交集，即树不存在环形结构
[3] 树的子树又称树的分支
[4] 树的定义是一个递归，即当n > 1时，除根以外的其他结点划分为m(m>0) 个互不相交的有限集T1, T2,… Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

树的示例如图1所示：

图1.树的示例

    依据图1中树的示例可以定义树的术语如下：

[1]  结点（node）——表示树中的元素，包括数据项及若干指向其子树的分支，图1中的A、B、C、D、E、F、G、H、I、J、K、L
[2]  结点的度（degree）——结点拥有的子树个数，图1中A节点的度为3，B节点的度为2，C节点的度为1，E节点的度为0
[3]  叶子（leaf）——度为0的结点，图1中节点E、G、H、I、J、K和L为叶子节点
[4]  树的度——一棵树中最大的结点度数(子树数），图1中树的度为3
[5]  孩子（children）——结点的子树的根称为该结点的孩子（结点），图1中节点B、C和D是节点A的孩子
[6]  双亲（parent）——孩子结点的上一层结点叫该结点的双亲(父结点)，A节点是节点B、C和D的双亲，B节点是节点E和F的双亲
[7]  兄弟（sibling）——同一双亲的孩子互称兄弟（结点），图1中BCD互称为兄弟
[8]  结点的层次——从根结点算起，根为第一层，它的孩子为第二层……，若当前节点所处的层数为i,则其子树的根节点（其孩子）所处的层数为i+1
[9]  树的深度（树高）——树中结点的最大层次数，图1中树的高度为4，注意：叶子节点未必都在树的最大层上
[10]  堂兄弟——其双亲在同一层的结点互称为堂兄弟。图1中EGH互为堂兄弟
[11]  结点的祖先（ancestor）——从根结点到该结点所经分支上的所有结点，图1中，EBA是K的祖先
[12]  结点的子孙——以某结点为根的子树中的任一结点都称之为该结点的子孙
[13]  叶子节点又称为终端节点，非叶子节点称之为非终端节点

森林：n（n≥0）颗独立的树构成的集合，通常情况下森林一般由多棵树构成，空树和非空树也为森林

由此可以看出森林和树都是递归式定义结构