离散数学中的M叉树

M-array Tree（M 叉树）可以被描述为二叉树的一种推广，其中每个节点最多有 M 个子节点。换句话说，如果一棵树的每个节点拥有的子节点不超过 m 个，则该树被称为 m 叉树。当 M = 2 时，二叉树被称为 M-ary tree（2 叉树）。通过下图，我们可以看到 M=3 的 M-ary tree 的一个例子。

M 叉树的类型

1. 如果 M 叉树的每个节点要么有 0 个子节点，要么有 M 个子节点，那么这棵树被称为满 M 叉树。
2. 如果这棵树的每个叶子节点都处于相同的深度，那么这棵树被称为完美树。
3. 如果 m 叉树的除最后一层以外的所有层都已填满，则该树被称为完全树。在完全树中，每个非叶子节点都有 M 个子节点。然而，如果最后一层树是不完整的，那么给定树的所有节点将尽可能靠左排列。

M 叉树的性质

M 叉树有各种性质，其中一些如下所述：

如果有一棵满 M 叉树，其中包含 i 个内部顶点，那么我们可以使用以下公式来计算该树的顶点数和叶子数：

例如：假设一棵树有 4 个内部顶点，且 m = 3。现在我们需要计算该树的顶点数和叶子数。

解答：根据题意，m = 3，i = 4，我们知道：

在 13 个顶点中，有一个根顶点，其余 12 个顶点是这 4 个内部顶点的子节点。

现在我们将使用以下公式计算树的叶子数：

因此，该树共有 13 个顶点和 9 个叶子。

遍历

二叉树和 M 叉树都具有相同的性质，如下所述：

前序遍历

在前序遍历过程中，我们首先访问根节点，然后遍历其子树，该子树包含左子树和右子树。因此，在访问根节点后，我们首先遍历左子树，然后遍历右子树。我们一次只能访问一个节点。“前序遍历”这个名字也指的是根节点在左子树和右子树之前被访问。在前序遍历中，时间复杂度为 O(n)。我们可以用以下形式表示前序遍历的过程：

后序遍历

在后序遍历过程中，我们将遵循左右根策略。在此策略中，我们将递归地遍历所有以子节点为根的子树。有两个子树：左子树和右子树。因此，我们首先遍历左子树，然后遍历右子树。只有在访问完所有子树后，我们才会访问根节点。“后序遍历”这个名字也指的是根节点在左子树和右子树之后被访问。在后序遍历中，时间复杂度也为 O(n)。我们可以用以下形式表示后序遍历的过程：

中序遍历

在中序遍历过程中，我们将遵循左根右策略。在此策略中，我们将首先遍历左子树，然后访问根节点，最后遍历右子树。“中序遍历”这个名字也指的是根节点位于左子树和右子树之间。在中序遍历中，时间复杂度也为 O(n)。我们可以用以下形式表示中序遍历的过程：

还有一种解释 m 叉树遍历的方法。二叉树和 m 叉树的遍历是相似的。但是，当 m > 2 时，一个节点可能包含两个以上的子节点，这时我们需要定义左子树和右子树的表示。我们可以通过将父节点的子节点列表分成两组来获得左子树和右子树。通过定义 m 个子节点的顺序，我们将一部分节点 {0, 1,... m/2} 构成左子树，将另一部分 {m/2, ...., m} 构成右子树。

存储 m 叉树的方法

我们可以通过两种方式存储 m 叉树：使用数组，或使用基于指针的方法。下面我们将一一解释：

数组：假设我们有一个完全 M 叉树。在这种紧凑的排列中，如果有一个索引 i，则可以通过其索引 m*i + c 来找到其在 {1,...., m} 范围内的第 c 个子节点。在这种情况下，此方法不会浪费空间。在此类方法中，空间复杂度将为 O(mⁿ)。

基于指针：每个节点必须有一个内部数组，以便该数组可以存储指向其 M 个子节点的指针。基于指针的实现方法与基于数组的实现方法相比，具有更高的空间复杂度。因此，基于指针的方法的空间复杂度为 O(m*n)。

将 m 叉树转换为二叉树

假设我们尝试将任意 m 叉树转换为二叉树。在这种情况下，我们需要使用一个常数因子，该因子只用于增加树的高度，而不会影响整体的最坏情况时间复杂度。首先，我们将通过链接给定父节点的所有中间子节点来形成一个链表。然后，我们将保留从父节点到第一个子节点（即最左子节点）的链接，并在此过程中删除到其他子节点的所有链接。

↓

↓

↓

M 叉树的应用

M 叉树有很多应用，其中一些如下所述：

1. M 叉树在颜色量化中有用。
2. 我们可以将其用于网格生成和图像处理。
3. 在自然语言处理应用中，我们将使用解析树和语法树。
4. 在渲染和碰撞检测中，我们可以使用游戏引擎。
5. 我们可以使用抽象语法树来表示程序代码的结构。
6. 我们可以表示文件系统数据结构。在此，节点用于表示文件和文件夹等，还有许多其他地方。

在下图，我们将以这种方式指示语法树的一个例子：