学科分类
目录
数据结构

什么是树

树是由n(n>=0)个结点组成的一个具有层次关系的有限集合。

如果n=0,它是一棵空树,这是树的特例;

如果n>0,它是一棵非空树。一棵非空树的示意图如图1所示。

图1 树

图1就是一棵非空树,树中的每个元素称为结点。

在任意一棵非空树中,存在且仅存在一个根结点,简称根,根结点只有后继结点而没有前驱结点,图6-1中的A结点就是根结点;

其余结点可以分为多个互不相交的有限集,每一个有限集又是符合定义的树,称为根的子树。如以B结点为根,是一棵树;以J结点为根,是一棵树。因此树也可以说是由树根和若干棵子树构成。

树的定义具有递归性,因为在树的定义中又用到了树的定义,这是树的固有特性,即一棵树由若干棵互不相交的子树构成,而每一棵子树又是由更小的子树构成。

学习树,就必须要要学习树的一些基本术语,比如根、结点、叶子等,接下来我们就来学习树的一些相关术语。

在一棵树中,每个结点的直接后继结点称为该结点的孩子结点(子结点)。相应的,该结点称为孩子结点的双亲结点(父结点)。具有同一父结点的结点互为兄弟结点。进一步推广,隔了代的兄弟结点称为堂兄弟结点,而在垂直关系上,它们又称为子孙结点。以图6-1中的树为例:

①A是B、C、D的父结点;B、C、D是A结点的孩子结点;

②B、C、D是兄弟结点;E、F、G是兄弟结点;I、J是兄弟结点;

③E、H、I是堂兄弟结点;K、L是堂兄弟结点;

④以B、C、D为根结点的子树上的所有结点都是A结点的子孙结点;

⑤A、B、F都是K结点的祖先结点(具有垂直的直系关系)。

在树中,一个结点拥有的子树的数目称为结点的度,如图6-1中根结点A的度为3,因为它有B、C、D(以这三个结点为根结点的子树)三棵子树;D结点的度为2,因为它有I、J两棵子树;C结点的度为1,它只有以H为根结点的一棵子树。

树中各结点度的最大值称为树的度,通常将度为m的树称为m次树。如图6-1是一棵3次树,因为所有结点中度的最大值为3。

在一棵树中,度不为0的结点称为非终端结点或分支结点,度为0的结点称为终端结点或叶子结点,也就是没有后继结点的结点就是叶子结点。如图6-1中的树,B、C、D、F等都是分支结点,而E、H、K、L等都是叶子结点。对于分支结点,其分支数就是该结点的度。

树中的结点都处在某一个层次中,树的层次从根开始定义,根为第一层,根的孩子为第二层,以此类推,结点所在层次为其父结点层次加1。而树的最大层次为树的高度或深度。图1中的树有4层,树的高度为4,如图2所示。

图2 树的层次与高度

若从树中的结点ki开始,沿着结点序列kikp…kj,可以找到结点kj,则称结点序列kikp…kj是从ki到kj的一条路径或道路,如图3所示。

图3 结点A到K的路径

在图3中,描粗的部分就是结点A到结点K的路径,所谓路径其实就是从一个结点到达另一个结点的路线。路径的长度是路线上所经过的边(连接两个结点的线段)的数目,等于结点个数减1。

注意:若一个结点序列是路径,则在树的树形图表示中,该结点序列“自上而下”地通过路径上的每条边,从树的根结点到树中其余各结点均只有一条唯一路径。

多棵树可以组成一个森林,森林就是m(m>=0)棵互不相交的树的集合。对于树来说,其子树的集合就是森林,例如图2中的树,删除根结点A之后,其子树就组成了一片森林。

如果一棵树中的结点,从左至右是有序的,不能互换,则称这棵树为有序树。否则称为无序树。若无特别指明,一般讨论的都是有序树。在有序树中,最左边的子树称为根的第一个孩子,最右边的称为最后一个孩子。

点击此处
隐藏目录