树的基本概念与基本性质介绍

简介

树由顶点（节点）和连接它们的边组成。与你之前学习的线性数据结构不同，树是分层的。它们类似于图，但环在树中不能存在。因此，树是无环的。换句话说，任意两个节点之间总是恰好存在一条路径。

• 根节点：没有父节点的节点。
• 子节点：连接到上层节点（即父节点）的节点。
• 父节点：拥有一个或多个子节点的节点。
• 兄弟节点：共享同一个父节点的节点。
• 叶节点：不包含任何子节点的节点。
• 祖先节点：从节点 d 到根节点路径上的所有节点。祖先节点包括节点 d 的父节点、祖父母节点等。

下图展示了上述所有术语：

说明：

在上图中，1 既是根节点，也是节点 2、3 和 4 的父节点。节点 3 是节点 6 和 7 的父节点。由于节点 2、3 和 4 共享同一个父节点 1，因此它们互为兄弟节点。同样地，6 和 7 也互为兄弟节点，因为它们的父节点都是 3。

其他术语与公式

树中还有一些常见的术语：

• 子树：子树是树的一部分，可以被视为一个独立的完整树。树中的任意一个节点及其下方所有相连的节点共同构成原树的一个子树。

• 节点的度：一个节点所拥有的子节点总数。

• 路径长度：路径中边的数量。

• 节点 n 的深度：从节点 n 到根节点的路径长度，根节点的深度为 0。

• 节点 n 的层级：(节点的深度) + 1

• 节点 n 的高度：从节点 n 到其最深后代节点的路径长度。整棵树的高度即为根节点的高度，而叶节点的高度始终为 0。

• 树的高度：根节点的高度

上图中共有六个子树，每个子树用数字标记。每个节点都有两个子树，分别是左子树和右子树。叶节点没有子树。

常见的树类型

存在多种类型的树，针对不同的应用场景进行了优化。每种树类型具有独特的结构，因此不同操作的时间和空间复杂度也各不相同。一些常用的树类型包括：

• 二叉树
• 二叉搜索树
• AVL 树
• 红黑树
• 2-3 树

你将在后续章节中详细学习这些类型！

N 叉树

在图论中，“N 叉树”是一种根节点树，其中每个节点最多有 N 个子节点。它也被称为“k 叉树”、“k 叉树”或“M 叉树”。二叉树是 k=2 的特殊情况。N 叉树最多可有 N 个子节点，最少可有 0 个子节点。二叉树被广泛应用于众多重要算法中！

快速小测验