数据结构：树

树（Tree）是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。这篇文章主要介绍树的相关概念、性质及数学推论。

概念

树是由 n（n≥0）个有限结点组成一个具有层次关系的集合，当 n=0 时，称这棵树为空树。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下性质：

• 每个结点都只有有限个子结点或无子结点
• 没有父结点的结点称为根结点
• 每一个非根结点有且只有一个父结点
• 除了根结点外，每个子结点可以分为多个不相交的子树
• 树里面没有环路(cycle)

相关术语

在学习树的过程中，你可能会遇到以下名词：
理解这些词应该优先从树或子树的角度出发。

• 结点
  树中的一个独立单元，之前我们说了，树是一个集合，结点就是这个集合中的一个元素。
• 结点的度
  结点拥有的子树数称为结点的度。
• 树的度
  树的度是树内各结点度的最大值。
• 叶子（叶子结点）
  度为 0 的结点称为叶子或终端结点。
• 非终端结点（分支结点）
  度不为 0 的结点称为非终端结点或分支结点。除根结点之外，非终端结点也称为内部结点。
• 双亲（双亲结点）、孩子（孩子结点）
  结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
• 兄弟（结点）
  同一个双亲的孩子之间互称兄弟。
• 祖先（祖先结点）
  从根到该结点所经分支上的所有结点。
• 子孙（子孙结点）
  以某结点为根的子树中的任一结点都称为该结点的子孙。
• 层次
  结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等千其双亲结点的层次加 1。
• 堂兄弟（堂兄弟结点）
  双亲在同一层的结点互为堂兄弟。
• 树的深度、树的高度
  树的深度或高度数值上等于树中结点的最大层次，深度以根结点为 1 向叶子结点递增，高度以叶子结点为 1 向根结点递增。
• 结点的深度、结点的高度
  结点的深度或高度数值上等于以该结点为根结点的子树的最大层次，深度以目标结点为 1 向叶子结点递增，高度以叶子结点为 1 向目标结点递增。
• 有序树和无序树
  如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
• 森林
  m (m≥0)棵互不相交的树的集合。
• 路径
  两个结点之间经过的结点序列，路径的方向为子结点指向子结点（自上而下）。
• 路径长度
  一条路径中经过的边的条数。
• n 叉树
  一棵树中允许结点拥有子树的最大数目，如二叉树允许一个结点最多可拥有两个子树。

形象描述

为了便于更形象的理解二叉树，我们可以用图形来表示树，通常用圆形表示一个结点，用线段表示结点之间的关系，下面的图中因为某些限制，结点之间的连接是折线，事实上用直线来连接更好一点，此外，连接是具有方向性的，为父结点指向子结点，你可以使用箭头线段来连接，一棵树看起来是这样的：

这棵树有 7 个结点，1 结点的度为 2，2 结点的度为 3，3 结点的度为 1，其他结点（4,5,6,7）的度为 0，这些度为 0 结点被称为叶子结点，其他结点为非终端结点（他们的度不为 0），整棵树的度为 3，深度也为 3。

树的存储结构

树的存储可以使用顺序存储或链式存储实现，顺序存储结构不是很灵活，通常用于储存特定的 M 叉树，如二叉树的存储可以使用顺序存储。最通用的方式是使用链式存储。无论哪种存储结构，其每个结点的结构都是相似的，都有数据区和指针区，因为一个结点可以有很多孩子结点，所以指针区相对于链表要复杂一点，如果说链表的每一个结点的指针域都指向空或者唯一的结点，而树中每一个结点的指针指向多少结点是不确定的。

双亲表示法

一个结点可能没有孩子结点，但一定有一个唯一的双亲结点（除根节点外），利用这个方式可以很快的找到双亲结点。但是如果仅仅是这样表示，只能连接两个结点，要表示一棵完整的树还需要指针将所有节点连接起来，最简单的方式是利用顺序存储结构，可以避免手动创建指针，当然，你也可以利用链表将他们连起来。

这种方法能方便的找到父节点，但要找到兄弟节点和孩子节点比较复杂。

孩子表示法

树的孩子表示法通过线性表来实现，首先将每个结点存入顺序表中，顺序表的每一个结点除了保存树中每个结点的信息，还包含一个指针域，指向该结点的直接子元素构成的链表。

这种方法可以很快的找到某个节点的孩子节点，但找到兄弟节点比较困难。

孩子兄弟表示法

孩子兄弟表示法完全采用链表实现，在链表的每一个节点中，有三个域，分别为孩子指针域、数据域、兄弟指针域，逻辑结构如下：

这种表示方法可以很轻松的查找兄弟很孩子节点，但查找父节点比较麻烦。

树的相关推论

结点拥有的结点数为所有结点的度数+1

证明：

由结点的度和孩子结点的概念可得，结点的度数=该结点孩子结点的个数

∵ 除根结点外其余结点都可以作为孩子结点

∴ 树的结点总数=孩子结点总数+根结点数=所有结点的度数+根结点数=所有结点的度数+1

一棵有 n 个结点的树有 n-1 条边（结点之间的连线）

证明：

∵ 树中除根结点外每个结点都有一个父结点，即这些结点都有一条线与父结点连接

∴ 边的数目为结点数减去根结点数 1

度为 m 的树中第 i 层最多有 m^i-1个结点（i≥1）

证明：

若考虑最多的情况，则每一个结点的度都为 m，即每一个结点都有 m 个孩子结点，即第 i 层的每一个结点在第 i+1 层都会产生 m 个孩子结点。

设N(i)为第 i 层的结点数，第 i+1 层结点数可表示为 N(i)×m

∵N(i)的个数为N(i-1)×m，可得 N(i+1)=N(i-1)×m×m

依次进行如上的转化，可得到N(i+1)=N(i-n)×mⁿ⁺¹

即 N(i)=N(i-n)×mⁿ

这是一个通式，知道任意一层结点的个数即可推出其他层结点的个数，最好考虑的是第一层

∵ N(1)=1

∴ 将上面的 i-n 化为 1

可得N(i)=N(1)×m^i-1

∴ 度为 m 的树中第 i 层最多有m^i-1个结点

代码验证：

Golang

package main

import (
    "fmt"
)

/*
degree：树的度
level：层序数
*/
func getNodeNum(degree, level int) int {
    if level != 1 {
        level--
        return getNodeNum(degree, level)*degree
    } else {
        return 1
    }
}

func main() {
    var degree, level int
    fmt.Printf("请输入树的度\n")
    fmt.Scan(&degree)
    fmt.Printf("请输入层序数\n")
    fmt.Scan(&level)
    nodeNum := getNodeNum(degree, level)
    fmt.Printf("度为%d的树中第%d层最多有%d个结点\n", degree, level, nodeNum)
    main()
}

从上面的数学证明过程中你应该就想到了用递归的方式实现，代码也是这样做的，让我们检验一下:

点击展开 >folded

请输入树的度
2
请输入层序数
9
度为 2 的树中第 9 层最多有 256 个结点
请输入树的度
3
请输入层序数
4
度为 3 的树中第 4 层最多有 27 个结点

根据检验，2^9-1=256，3^4-1=27，再次证明度为 m 的树中第 i 层最多有 m^i-1个结点。

顺便提一句，当度为 2 时，讨论极限条件，这棵树是满二叉树，根据这个结论可以得出它的性质：第 i 层有 2^i-1个结点，这在以后的文章中便不做推导了。

高度为 h 的 m 叉树至多有 (m^h-1)÷(m-1)个结点

这个推论接着上一条结论继续往下推，高度为 h 实际上是告诉了我们这棵树的层数，考虑至多的极限情况，m 就是上一条结论中的度，实际上证明这个推论只需要将每一层的结点数求和，首先将每一层的结点数构造成等比数列，再按等比求和公式求和：

证明：

考虑最多情况，m 叉树的每一个结点都会在下一层产生 m 个结点

设N(h)为第 h 层的结点数，第 h+1 层结点数可表示为 N(h)×m

设数列{a_h}，a₁=N(1)，a₂=N(2)，a_h=N(h)，a_h+1=N(h+1) (h≥1)

由条件可知a₁=N(1)=1

∵a_h+1÷a_h=N(h+1)÷N(h)=m，h≥2

根据定义，数列{a_h}是以首项为1，公比为m(m>0)的等比数列

设数列{a_h}的前n项和为S_h

由求和公式

$$
S_n=\frac{a_1\times(1-q^n)}{1-q}, (q\neq1)
$$

a₁=1，q=m，m≠1，n=h

可得

$$
S_n=\frac{(1-m^h)}{1-m}
$$

具有 n 个结点的满 m 叉树的最小高度为 log_m(n(m-1)+1)

证明：

考虑极限条件，要求得最小高度，就需要将每一层填满，之前我们已经证明了 m 叉树每一层的最大结点数，这其实是上一个结论的逆向问题，同样的先将每一层的结点数构造成数列，转换为数学问题就是已知通项公式，前 h 项和，求 h 的值，这个证明这个结论需要做的就是得出通项公式和前 h 项和，通项公式在证明上一个结论时已经得出，进而可以得出前 h 项的和为

$$
S_h=\frac{(1-m^h)}{1-m}
$$

令 S_h=n 反解出 h

$$
h=\log_m{(n(m-1)+1)}
$$

本文作者：KylinLee

本文链接：https://kylin.dev/2020/07/12/数据结构：树

版权声明：本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。