树的基础概念与基本性质简介！

引言

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

• 根节点：没有父节点的节点。通常情况下，树并不一定必须有根节点。然而，有根树有一个特殊的节点作为根，这正是本课程中我们将主要使用的类型。
• 子节点：连接到上层节点（即父节点）的节点
• 父节点：拥有一个或多个子节点的节点
• 兄弟节点：共享同一个父节点的节点
• 叶节点：没有子节点的节点
• 祖先节点：从某个节点 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 个子节点。二叉树在众多重要算法中被广泛应用！

测验时间！