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

简介

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

• 根节点：没有父节点的节点。
• 子节点：连接到上层节点（即父节点）的节点。
• 父节点：拥有一个或多个子节点的节点。
• 兄弟节点：共享同一个父节点的节点。
• 叶节点：没有子节点的节点。
• 祖先节点：从某个节点 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 时，每个节点最多可有 2 个子节点，最少可有 0 个子节点。二叉树被广泛应用于众多重要算法中！