数据结构之树的相关术语

素颜马尾好姑娘i 2023-01-01 08:53 155阅读 0赞

树的定义：

①如果树的结点个数为0，则树为空树

②如果树的结点个数为1，则该结点是被称为根结点的结点

③如果树的结点个数大于1，则必存在一个称为根的结点，它的分支下是几个互不相交的有限集合，并且这些互不相交的有限集合本身又是一棵树。

定义注释：从定义③可知，树的定义蛮有趣的，树中有树，树中还是树，所以可知树的定义是一个递归定义，从下图可以看出，如果你仔细分析过带简单循环体的递归程序，那么会知道程序的整个运行路径其实就是一棵树，所以树和递归还是有不浅的联系的。

![70][]

（1）结点（node）

树的结点由数据元素及其若干分支组成，如下图所示：

![70 1][]

（2）树和子树(subtree)

以根结点为根的树为全树（或树），以其他结点作为根结点的树为子数

![70 2][]

所以当谈到以哪个结点为根结点，就应该知道指的是哪棵子数，以一个结点作为根结点的子数是唯一的。

（3）结点的度（degree of node）

结点的度指的是结点分支的个数，如下图所示：

![70 3][]

（4）树的度

选取所有结点中最大的度，就是树的度，如下图所示：

![70 4][]

（5）叶子结点(leaf node)

度为0的结点就是叶子结点，它位于树最深层，并且树只要非空，就一定存在叶子结点，如下图所示：

![70 5][]

（6）分支结点（internal node）

度大于0的结点为分支结点，显然除了叶子结点之外的结点都为分支结点。

![70 6][]

而且根结点也是分支结点。

（7）父节点（father node）和子结点（child node）

一个结点若干分支下的结点都为该结点的子结点（或称孩子（children）），并且，该结点称为子结点的父节点，如下：

![70 7][]

（8）兄弟结点(brother)和堂兄弟结点

父节点下的所有子结点互为兄弟结点，如下图，B，C，D结点互为兄弟结点

![70 8][]

堂兄弟结点：位于同一层的，并且父节点之间是兄弟结点的结点互为堂兄弟结点，上图中，E，G为堂兄弟结点，F和G也是堂兄弟结点，他们的父节点是兄弟结点。

（9）祖先(ancestor)和子孙(descendant)

这个关系就同父亲和孩子一样。从根结点到该结点路径上的所有结点都为该结点的祖先，如下图所示：

![70 9][]

反之，C,G，H就是A的子孙，G和H都为C的子孙，H也可以称为G的子孙，不过因为G和H只隔一代，所以一般称为孩子

![70 10][]

所有的结点都有一个公共祖先，就是根结点，但任意两个结点可以不只一个祖先，比如E和F的公共祖先有A和B

（10）路径(path)

从一个结点到另一个结点之间的边和结点构成路径，如下图：

![70 11][]

A到H的路径包含A，C，G，H结点和连接这些结点的三条边

（11）子树根结点

如图，A的子树根结点为B,C,D。B的子树根结点为E,F，D没有子树根结点

![70 12][]

（12）层次（level）

树是一个递归结构，所以也有层次这种概念，由层次也会引发出树的深度，就好像递归也有深度一样。结点的层次为从结点到根结点的路径中边的条数，并且认为根结点的层次为0，因为根结点到自身的路径中边的条数为0（但也有一些教科书假设根结点的层次为1，这个时候要注意书中相应的说明），如下图所示，B的层次为1，G的层次为2，H的层次为3

![70 13][]

结点的层次有时也称为结点的深度(depth)

(13)树的深度

与树的度对应于结点的度一样，树的深度也是选取结点中的最大深度（或最大层次），下图的树的深度为3

![70 14][]

树的深度是一个自顶向下的概念，是从根结点出发，向着叶子结点方向前进的，并且深度这个概念一般只用来描述树，当描述结点的深度时，层次更为恰当，但是用深度也无妨。

![70 15][]

（14）结点的高度（height of node）

高度与深度不同，高度的描述是自下向顶的，而深度是自顶向下的，同一层次的结点的高度是可以不同的，下面先来介绍高度的概念。

从一个结点出发，一直到它的叶子结点的最大路径中的边的条数，就是该结点的高度，叶子结点的高度认为是0，因为从叶子结点出发，到它本身的路径只有一条，并且边数为0。下图标出了所有结点的高度，可以观察到，同一层次的叶子结点的高度不一定相同，因为它们的叶子结点的最大层次是不同的。

![70 16][]

这里，由于A结点到叶子结点的最大路径为A->C->G->H,而不是A->B->E(F)和A->D，所以它的高度是3，因为最大路径的边数为3

（15）树的高度

树的高度就是根结点的高度，如上图所示，该树的高度为3

（16）森林（forest）

森林的概念和树的概念是密切联系的。

森林就是彼此不相交的树的集合，树也可以看成是森林共有一个根结点后的结构，如下图所示：

![70 17][]

上图标记出来的就是三棵子树，他们构成一个（子树）森林，如果给这三棵子树共有一个结点，那么就构成一个树

![70 18][]

这个树是A，森林是子树B，C，D的集合，可以看出森林和树是两个密切相关的概念。

[70]: /images/20221120/7cc3a88b36ac4e369b0104398f8aed60.png
[70 1]: /images/20221120/5299f5fdf9c1421ba059c6e86b66f764.png
[70 2]: /images/20221120/32396ae07b2a42f79849665e493c5100.png
[70 3]: /images/20221120/071a7c87e59f4723ac73f9ab5a2eda4e.png
[70 4]: /images/20221120/eecdd873f22947b4a6bcf4b5b2e33a24.png
[70 5]: /images/20221120/5e5de527b762420680b73fb783b4d68d.png
[70 6]: /images/20221120/5e8476869d5e415e92dd06b6a1b4d51e.png
[70 7]: /images/20221120/a6cecc9056b74d0ba543c63f311d25a8.png
[70 8]: /images/20221120/28ed25d495d9443d9499fd3262df6a76.png
[70 9]: /images/20221120/8932f7107b2d40bd9b0c3761aa3f8f74.png
[70 10]: /images/20221120/a9272ed72ed04fda9f2a634f44b53945.png
[70 11]: /images/20221120/24d09df44248457aa4c436e2b0725dec.png
[70 12]: /images/20221120/c9e6160eadd3469c95349412a7390ec7.png
[70 13]: /images/20221120/8ee86d8099a54fa3bafa3cbdb92339f9.png
[70 14]: /images/20221120/ecb8c7c1bc8d4ccbb0f69e639658dbe5.png
[70 15]: /images/20221120/b21c0e23d2e541468227c87ff8b15f0f.png
[70 16]: /images/20221120/294ac36ce29f4a48b0d1759b265d2df4.png
[70 17]: /images/20221120/d83034c9de6147198a21e91758da20f5.png
[70 18]: /images/20221120/8b68be003866444ca706d596150864bc.png