树及其基本性质

简介

树由顶点（节点）和连接它们的边组成。与我们之前学习的线性数据结构不同，树是层次化的结构。树与图类似，但树中不能存在环路，即树是无环的。换句话说，任意两个节点之间始终有且仅有一条路径。

• 根节点：没有父节点的节点。通常情况下，树并不一定必须有根；但本课程主要使用具有一个特定根节点的有根树。
• 子节点：与上层节点（父节点）相连的节点
• 父节点：拥有一个或多个子节点链接的节点
• 兄弟节点：具有相同父节点的节点
• 叶节点：没有子节点的节点
• 祖先节点：从某个节点 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-ary 树 或 M 叉树。二叉树是 N=2 的特殊情况，每个节点最多有 2 个子节点，最少可以有 0 个子节点。二叉树被广泛应用于众多重要算法中！