Part 2.4：树结构基础：从根到叶的层次艺术

引言：超越“一维”的思考

到目前为止，我们接触的数据结构——数组、链表、栈、队列——都是线性的。它们像一根线，元素一个接一个地排列。然而，现实世界中的许多关系并非如此简单。家族的族谱、公司的组织架构、计算机的文件系统……这些都呈现出一种层次化的结构。为了在程序中高效地表示和处理这种层次关系，我们引入了一种全新的、强大的非线性数据结构——**树 (Tree)**。

树是什么？ 它是一种模拟了自然界中树的形态的数据结构，由一个“根”节点和若干“子树”构成，完美地表达了“一对多”的层次关系。

为什么树结构如此重要？

• 面试价值：树是算法面试中当之无愧的“主角”。从二叉树的遍历，到二叉搜索树、平衡树、再到 Trie 树，几乎所有一线公司的面试都会深入考察你对树的理解和应用。掌握了树，就等于掌握了通往大厂 Offer 的半张门票。
• 工程价值：树结构在计算机科学中无处不在：
  • 文件系统：你的电脑文件夹就是一棵树。
  • 数据库索引：高效的数据库查询严重依赖 B-Tree 或 B+ Tree。
  • 前端开发：网页的 DOM 结构本身就是一棵 DOM 树。
  • 网络路由：路由器通过生成树协议来避免网络环路。
  • 人工智能：决策树是机器学习中的一种基本模型。

本文将作为你进入“树”世界的第一站，为你系统梳理树的核心概念、术语、分类和存储方式，为你后续学习更复杂的树算法铺平道路。

1. 树的核心原理与术语

直觉：一棵倒挂的家族树

理解树最直观的方式，就是把它想象成一棵倒挂的家族树。最顶上是“老祖宗”（根节点），往下是他的孩子们，孩子们又有自己的孩子……无限延伸。这个结构清晰地展示了辈分和亲属关系。

严谨原理：节点与边的集合

在计算机科学中，树被定义为一个由 n (n>=0) 个有限节点 (Node) 组成的集合，这些节点通过边 (Edge) 连接。它满足以下条件：

1. 有且仅有一个特定的节点被称为**根 (Root)**。
2. 当 n > 1 时，其余节点可分为 m (m>0) 个互不相交的有限集合 T₁, T₂, …, Tₘ，其中每一个集合本身又是一棵树，并被称为根的**子树 (Subtree)**。

这个定义是递归的，也是理解树相关算法（尤其是递归算法）的关键。

关键图示与术语大全

以上是学习树结构必须掌握的核心术语

2. 树的重要分类

2.1 二叉树 (Binary Tree)

二叉树是树结构中最重要、最常用的一种，是后续学习所有高级树结构的基础。

定义：每个节点最多有两个子节点，分别称为左子节点 (Left Child) 和 右子节点 (Right Child)。这两个子节点是有序的，不能互换。

特殊的二叉树

1. **满二叉树 (Full Binary Tree)**：一棵深度为 k 且有 2^k - 1 个节点的二叉树。除了叶子节点，每个节点的度都为 2。

   

2. 完全二叉树 (Complete Binary Tree)：深度为 k，除了第 k 层外，其他各层 (1 到 k-1) 的节点数都达到最大个数，第 k 层所有的节点都连续集中在最左边。

   

   重要特性：满二叉树一定是完全二叉树，但反之不成立。完全二叉树非常适合用数组来存储。

3. **二叉搜索树 (Binary Search Tree, BST)**：一种特殊的二叉树，满足：

   • 左子树上所有节点的值均小于其根节点的值。
   • 右子树上所有节点的值均大于其根节点的值。
   • 左右子树也分别为二叉搜索树。
     我们将在后续章节详细讲解。

4. **斜树 (Skewed Tree)**：所有节点都只有左子节点或右子节点，形态退化成一个链表。这是树的最坏情况。

2.2 其他树

• **N 叉树 (N-ary Tree)**：每个节点最多有 N 个子节点。
• **平衡树 (Balanced Tree)**：如 AVL 树、红黑树，能通过自平衡操作，确保树的高度维持在 O(log n)，从而保证高效的查找性能。
• B 树 / B+ 树：多路搜索树，常用于数据库和文件系统的索引。

3. 树的存储方式

3.1 链式存储法

这是最直观、最常用的存储方式。每个节点是一个对象，包含数据域和指向其子节点的指针。

伪代码：二叉树节点

class TreeNode:
  data // 节点存储的数据
  leftChild // 指向左子节点的指针
  rightChild // 指向右子节点的指针

Python 实现

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 手动构建一棵树
#      1
#     / \
#    2   3
#   /   / \
#  4   5   6

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)

优点：空间利用率高，增删节点灵活。
缺点：无法快速访问特定节点，需要遍历。

3.2 数组（顺序）存储法

这种方法通常只适用于完全二叉树，因为它能完美地利用数组索引的数学关系，不浪费空间。

原理：将树的节点按层序遍历的顺序存入一个数组中。

索引关系 (假设根节点索引为 0)：

• 节点 i 的父节点索引：(i - 1) // 2
• 节点 i 的左子节点索引：2 * i + 1
• 节点 i 的右子节点索引：2 * i + 2

关键图示：完全二叉树的数组表示

完全二叉树的层序遍历序列与其数组表示完全对应

优点：

• 节省了存储指针的额外空间。
• 可以 O(1) 时间找到父子节点。
• 缓存友好。
  缺点：
• 只适用于完全二叉树。对于非完全二叉树，会浪费大量空间。
• 增删节点不方便。

应用：堆 (Heap) 这种数据结构就是一棵完全二叉树，通常用数组来实现。

4. 复杂度与优劣势

复杂度

树的大部分操作（查找、插入、删除）的复杂度都与树的高度 h 相关。

• **最好情况 (平衡树)**：树的形态接近完全二叉树，高度 h = log₂n。此时，操作的时间复杂度为 O(log n)。
• **最坏情况 (斜树)**：树退化成链表，高度 h = n。此时，操作的时间复杂度为 O(n)。

这就是为什么平衡对于树结构如此重要的原因。

优势与劣势

• 优势：
  • 能高效地表示层次化数据。
  • 在平衡状态下，查找、插入、删除的效率非常高 (O(log n))。
• 劣势：
  • 在非平衡状态下，性能会急剧退化。
  • 实现和维护比线性结构更复杂。
  • 空间上需要额外的指针开销（链式存储）。

5. 总结与下一步

今天，我们打开了非线性数据结构的大门，系统地学习了树的基础知识。

• 核心：树是一种表示层次关系的递归数据结构。
• 关键：理解节点、根、父子、深度、高度等核心术语是基础。
• 重点：二叉树是最重要的一种树，其下的完全二叉树和二叉搜索树是重中之重。
• 实现：链式存储最通用，数组存储在完全二叉树（如堆）场景下更高效。
• 性能：树操作的性能取决于其高度，维持平衡是保证 O(log n) 效率的关键。

掌握了这些基础概念，我们就有了探索这片广阔森林的地图。在下一篇文章中，我们将学习树结构中最核心、最高频的算法——树的遍历，包括前序、中序、后序和层序遍历，它们是解决几乎所有树相关问题的基础。