树

树是一种非线性的数据结构，由节点和边组成，存在唯一根节点，每个节点可以拥有多个子节点，无环路；适合表达层级、从属关系，常用于文件目录、二叉搜索、排序索引等场景。

January 1, 1968数据结构1分钟阅读

在数据结构中，树（Tree） 是一种非常经典且高效的非线性、层级化（Hierarchical）数据结构。

如果把数组、链表比作排成一队的“线性”序列，那么树就像是自然界中的大树反过来放置——从一个“根”开始，向上（或向下）不断分支。它非常适合用来表示具有层级关系或包含关系的数据（例如电脑里的文件目录、公司的组织架构图）。

图（Graph） 是由节点（Vertex/Node）和连接节点的边（Edge）构成的极度自由的数据结构。边可以是单向的（有向图），也可以是双向的（无向图）；节点之间可以任意连接，甚至形成环路。

如果给一个无向图加上以下几个限制，它就变成了一棵树：

连通性（Connected）： 任意两个节点之间都必须有路径相连（不能有孤立的节点或离散的块）。
无环性（Acyclic）： 树里绝对不能有环（不能走着走着绕回原点）。
边的数量约束： 如果树包含 $N$ 个节点，那么它恰好只有 $N - 1$ 条边。少一条就会断开，多一条就必将产生环。

手绘示意图，数据结构树 Tree 与图 Graph 对比，树不存在环，图可以包含环路 — 数据结构对比：树 (Tree) 与图 (Graph)，树是无环连通图，图允许存在回路

为了更清晰地理解，我们可以从结构特点上做个对比：

特性	图（Graph）	树（Tree）
形态本质	多对多关系（复杂的网络）	一对多 / 层级关系（树状/金字塔）
根节点	没有根的概念，所有节点地位平等	有且仅有一个根节点（Root）
路径唯一性	两个节点之间可能有多条路径	任意两个节点之间有且仅有一条简单路径
父子关系	无父子概念	有明确的父节点、子节点、兄弟节点关系
环（Cycle）	可以包含环，也可以不包含	绝对不允许包含环

树是由 $n$ （ $n \ge 0$ ）个节点组成的有限集合。当 $n = 0$ 时，称为空树。

树的节点之间通过“父子关系”相连，其核心组成元素包括：

根节点（Root）：树最顶端的节点，没有父节点（一棵非空树有且仅有一个根节点）。
父节点（Parent） 与 子节点（Child）：如果节点 A 直接连接到节点 B，且 A 在上层，则 A 是 B 的父节点，B 是 A 的子节点。
兄弟节点（Sibling）：拥有同一个父节点的节点互为兄弟节点。
叶子节点（Leaf）：没有子节点的终端节点（处于树的最底层）。
边（Edge）：连接父节点与子节点的线。

树数据结构术语示意图，标注根节点、父节点、子节点、兄弟节点、子树、叶子节点、层级、树高、边 — 树数据结构基础术语图解，包含根、叶子、子树、层级、树高等概念

核心规则：树中不能存在环路（Cycle），且每个子节点有且仅有一个父节点。如果打破了这个规则，树就会退化或变成“图”。

度（Degree）：
- 节点的度：一个节点拥有的子节点数量。
- 树的度：整棵树中所有节点度的最大值。
深度（Depth）：从根节点到某个节点的唯一路径上的边数（根节点的深度通常定义为 0 或 1）。
高度（Height）：从某个节点到其最远叶子节点的最长路径上的边数（整棵树的高度即为根节点的高度）。
层（Level）：根节点为第 1 层（或第 0 层），其子节点为第 2 层，以此类推。

在 C++ 中，最典型的二叉树表示方式是利用指针（指向动态分配的子节点）：

#include <iostream>

// 1. 定义二叉树节点结构
struct TreeNode {
    int val;            // 节点数据
    TreeNode* left;     // 指向左子树的指针
    TreeNode* right;    // 指向右子树的指针

    // 构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 2. 经典的前序遍历（根 -> 左 -> 右）
void preOrder(TreeNode* root) {
    if (root == nullptr) return;

    std::cout << root->val << " "; // 访问根节点
    preOrder(root->left);         // 递归遍历左子树
    preOrder(root->right);        // 递归遍历右子树
}

// 3. 经典的二叉树构建与测试
int main() {
    /*
         构造如下二叉树:
              1
             / \
            2   3
    */
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);

    std::cout << "前序遍历结果: ";
    preOrder(root); // 输出: 1 2 3

    return 0;
}

如果一棵树中，每个节点的所有子节点之间都有严格的从左到右的次序关系，不能随意颠倒，那么这棵树就称为有序树（Ordered Tree）；反之则称为无序树。

二叉树（Binary Tree）是数据结构中最重要的一种树形结构。它是一种特殊的有序树，满足以下两个约束：

度的限制：任意节点最多只能有两个子节点（即节点的度最大为 2，可以是 0 个、1 个或 2 个）。
严格区分左右：子节点有明确的左子树（Left Subtree）和右子树（Right Subtree）之分，次序不能颠倒。

二叉树六种类型对比示意图，普通二叉树、满二叉树、完全二叉树、完美二叉树、平衡二叉树、二叉搜索树 — 二叉树的不同类型对比：普通二叉树、满二叉树、完全二叉树、完美二叉树、平衡二叉树、二叉搜索树

二叉树由于分支少（最多两个）、形态规整，非常适合用指针或静态数组进行存储，是绝大多数高效检索与优先级结构的基础。

二叉搜索树（BST, Binary Search Tree）
- 设计原理：利用“左小右大”的有序性（左子树 $<$ 根节点 $<$ 右子树）。
- 应用场景：基础查找表、范围查询。
自平衡二叉搜索树（AVL 树 & 红黑树）
- 设计原理：在 BST 的基础上增加“平衡因子”或“颜色标记”限制，防止树退化成单向链表，将查找、插入、删除的时间复杂度硬性锁定在 $O(\log n)$ 。
- 工业应用：
  - 红黑树：C++ STL std::map / std::set、Java TreeMap、Linux 内核调度器（CFS）。
  - AVL 树：只读或读多写少的内存索引。
堆（Heap / 优先队列 Priority Queue）
- 设计原理：利用完全二叉树的规整形态，直接映射到一维连续数组中（不需要任何指针开销，节点 $i$ 的左孩子为 $2i+1$ ）。满足“父节点总是大于（或小于）子节点”。
- 工业应用：
  - std::priority_queue（优先队列）。
  - 堆排序（Heap Sort）、Dijkstra 最短路径算法、Top-K 检索问题。
线段树（Segment Tree）与树状数组（Fenwick Tree）
- 设计原理：将区间按二叉树方式递归二分，每个节点保存该区间的统计信息（如区间和、区间最大值）。
- 工业应用：计算几何、高频区间更新与动态求和查询（ $O(\log n)$ 内完成）。

当树的度放宽到大于 2 时，借助“有序”的特性，可以设计出处理字符串与海量磁盘数据的高性能结构。

字典树（Trie / 前缀树）
- 设计原理：一棵多叉有序树，节点的路径承载字符串的字符。根节点到某一节点的路径组合起来就是一个前缀或单词。利用公共前缀减少冗余比较。
- 工业应用：
  - 搜索引擎的输入自动补全（Auto-complete）。
  - 路由表的 IP 最长前缀匹配、拼写检查器。
B 树 / B+ 树（B-Tree / B+ Tree）
- 设计原理：多路平衡有序查找树（一个节点可以有几百个有序的子节点）。利用大节点尺寸对齐磁盘块（Disk Block），极大地降低树的高度，减少磁盘 I/O 次数。
- 工业应用：
  - 数据库索引：MySQL (InnoDB 引擎)、PostgreSQL。
  - 文件系统：NTFS、Ext4、Btrfs。
后缀树（Suffix Tree）与 AC 自动机（Aho-Corasick Automaton）
- 设计原理：将字符串的所有后缀构造成一棵有序树，或在字典树的基础上增加失败指针。
- 工业应用：生物信息学中的 DNA 序列比对、文本编辑器中的多模式字符串匹配（如敏感词过滤）。

从“图”到“树”

树的基本定义与组成

树的关键术语

树的表示

有序树与二叉树

基于二叉树衍生出的数据结构

基于通用有序树（多叉树）衍生出的数据结构