1. 概述
在本篇文章中，我们将详细解析两种常见的树形数据结构：二叉树（Binary Tree） 与 二叉搜索树（Binary Search Tree）。
我们将分别介绍它们的定义、特性、示例结构，并通过对比帮助你理解它们之间的核心区别。文章面向有一定数据结构基础的开发者，因此不会过多讲解基础概念。
2. 二叉树简介
二叉树是一种每个节点最多有两个子节点的树结构，通常称为左子节点和右子节点。它由三类节点组成：
- 根节点（Root Node）：树的顶层节点
- 中间节点（Parent Node）：除根节点外，有子节点的节点
- 叶子节点（Leaf Node）：没有子节点的节点
如下是一个典型的二叉树结构：
我们以树 T₁ 为例：
- 节点
1是根节点 - 节点
4,5,6是叶子节点 - 节点
2,3是中间节点
每个节点通常包含三个部分：
- 左子节点指针
- 数据域
- 右子节点指针
其逻辑结构表示如下：
二叉树的常见变种包括：满二叉树、完全二叉树、斜树、平衡二叉树等。二叉树支持的基本操作有：查找、插入、删除、遍历。
3. 二叉树的特性
以下是二叉树的一些重要特性，理解它们有助于更好地掌握其结构与行为。
✅ 高度为 h 的二叉树最多有 2^h - 1 个节点
例如树 T₁ 的高度为 3，则最多有 2³ - 1 = 7 个节点。
✅ 若已知节点总数 N，则最小高度为 ⌈log₂(N + 1)⌉
树 T₁ 有 6 个节点，最小高度为 ⌈log₂(6 + 1)⌉ = 3。
✅ 第 L 层最多有 2^L 个节点
根节点位于第 0 层，所以第 0 层最多只有 2⁰ = 1 个节点。
✅ 若有 L 个叶子节点，则至少有 ⌈log₂L⌉ + 1 层
树 T₁ 有 3 个叶子节点，则至少有 ⌈log₂3⌉ + 1 = 2 层。
✅ 若所有节点的子节点数为 0 或 2，则子节点数为 2 的节点数比叶子节点数少 1
树 T₁ 有 3 个叶子节点，2 个有两个子节点的节点，符合该性质。
4. 二叉搜索树简介
二叉搜索树（Binary Search Tree, BST） 是一种有序的二叉树结构，具有以下额外特性：
- 每个节点最多有两个子节点
- 左子树中所有节点的值 < 当前节点的值
- 右子树中所有节点的值 > 当前节点的值
如下是一个有效的 BST 示例：
我们以该树为例：
- 根节点为 8
- 左子树节点值均小于 8，右子树节点值均大于 8
- 整个树结构满足 BST 的有序性要求
再来看一个不是 BST 的二叉树示例：
虽然结构上是二叉树，但左子树中存在大于根节点的值（如 7 > 6），因此不满足 BST 的定义。
BST 是一种非常高效的查找结构，支持快速的插入、删除和查找操作（平均时间复杂度为 O(log n)）。
5. 二叉树与二叉搜索树的区别
| 特性 | 二叉树（Binary Tree） | 二叉搜索树（Binary Search Tree） |
|---|---|---|
| 结构定义 | 每个节点最多两个子节点 | 在二叉树基础上增加有序性约束 |
| 是否有序 | 无序 | 有序（左子树 < 根 < 右子树） |
| 是否 BST | 不一定是 BST | 一定是二叉树 |
| 节点组织 | 无需组织节点 | 必须按值排序组织节点 |
| 操作效率 | 插入、查找、删除效率较低 | 插入、查找、删除效率高 |
| 应用场景 | 构建其他树结构（如堆、红黑树） | 快速查找、排序、动态集合操作 |
⚠️ 注意：虽然 BST 操作效率高，但如果树不平衡（如退化成链表），性能会下降至 O(n)，需要通过平衡策略（如 AVL、红黑树）来优化。
6. 总结
| 关键点 | 说明 |
|---|---|
| ✅ 二叉树 | 每个节点最多两个子节点，结构灵活但无序 |
| ✅ 二叉搜索树 | 是二叉树的有序变种，支持高效查找 |
| ⚠️ BST 踩坑点 | 若树不平衡，性能会显著下降 |
| ✅ 使用建议 | 若需要频繁查找，优先考虑 BST；若仅需结构化存储，可使用普通二叉树 |
通过本文的对比与示例，相信你对二叉树与二叉搜索树的核心差异有了更清晰的认识。在实际开发中，选择合适的数据结构可以显著提升程序性能。