🌳 树与二叉树：从入门到深入解析

1. 引言

树，是计算机科学中关键的非线性结构，用于高效地组织和处理层级关系数据。对于初学者而言，掌握树与其最经典的形式——二叉树，更是后续深入算法与数据结构的基石。

2. 树的基本概念与术语 📚

• 节点（Node）：包含数据和指向子节点的引用。
• 根节点（Root）：结构的入口，唯一且无父节点。
• 边（Edge）：用于连接父节点与子节点。
• 父节点 / 子节点：结构中的上下级关系。
• 叶子节点（Leaf）：无任何子节点的节点。
• 内部节点（Internal Node）：拥有至少一个子节点的节点。
• 深度（Depth）/ 高度（Height）：节点到根的边数 / 树最长路径的边数 (Shibu Meher, 数字分析, crio.do, GitHub)。

3. 二叉树详解

3.1 定义

二叉树是特殊树，每个节点最多拥有两个子节点——左孩子和右孩子 (博客园)。

3.2 表示方式

1. 链式（节点+指针）
   支持动态增删，适合稀疏树结构 (Shibu Meher)。

   适用于完全/满二叉树，通过下标计算父/子节点位置 (GeeksforGeeks)。

4. 二叉树的属性

• 最大节点数：第 i 层最多 2^i 个节点
• 高度为 h 的二叉树最多有 2^(h+1)−1 个节点 (博客园, WsCube Tech)。
• 某些节点关系公式：叶子节点 = 唯一具有两个子节点的节点数 + 1 (博客园)。

5. 二叉树的类型

按结构划分：

• 满二叉树：每个节点要么有 0 或 2 个子节点。
• 完全二叉树：除最末层外，层级被填满，且最后一层从左至右填充。
• 完美二叉树：所有叶子位于同一层，内部节点都是双子节点。
• 斜树（Skewed Tree）：每个节点只有一个子节点，形同链表。
• 平衡二叉树：左右子树高度差 ≤ 1 (博客园)。

按值/用途划分：

• 二叉搜索树（BST）：左子树值小，右子树值大。
• 自平衡树：如 AVL、红黑树、Splay 树。通过旋转保持平衡，最坏操作时间 O(log n) (维基百科)。
• 堆结构：如最大/最小堆，用于优先队列等。

6. 常见操作与遍历

6.1 遍历方法

• DFS（深度优先）：

  • 前序：根→左→右
  • 中序：左→根→右
  • 后序：左→右→根

• BFS（广度优先）：层序，从上至下，从左到右 (博客园, 维基百科)。

6.2 构建与变动

• 插入/删除：BST 中插入按规则递归，删除节点时需考虑子节点数量。
• 旋转：用于自平衡树调整（左旋/右旋）保持高度平衡 (维基百科, 维基百科)。

7. 应用与优势

• 快速检索、排序、路径查找
• 基础结构：BST、AVL、红黑树、堆、哈夫曼树
• 系统应用：虚拟内存、索引、编译语法分析、优先队列 (Undercode Testing)

优点：结构清晰、动态；平均/最坏查找为 O(log n)（若平衡）。
局限：高度不平衡时耗时退化至 O(n)；旋转保持平衡需额外开销。

8. 用 C 实现一个简单的二叉树

下面是使用 C 语言进行节点创建与中序遍历的代码示例：

struct Node {
    int data;
    struct Node *left, *right;
};
struct Node* newNode(int val) {
    struct Node* n = malloc(sizeof(struct Node));
    n->data = val; n->left = n->right = NULL;
    return n;
}
void inorder(struct Node* root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

更全面的操作（插入、删除、旋转等）可参考 Shibu Meher 的文章 (Shibu Meher)。

9. 总结与学习路径

1. 从树认识起 → 理解节点、边、层级。
2. 掌握二叉树经典结构 → 各种类型与作用。
3. 精通操作方法 → 插入、删除、遍历、旋转。
4. 深入自平衡机制 → 学习 AVL、红黑树等高级算法。
5. 动手练习 → 从简单 C 实现到复杂平衡树，扎实基础。

📌 小贴士

• 中序遍历 + BST 属性 = 值有序输出
• 平衡树在现实项目中用于数据库索引、缓存机制
• 排查结构问题时绘制“树图”更直观，助理理解

🔗 推荐参考

• 最新 GeeksforGeeks 二叉树教程（2025年6月更新）(GeeksforGeeks, 博客园)
• Shibu Meher 的“Binary Trees using C”深度剖析（2025年4月）(Shibu Meher)
• Stanford CS106B 二叉树课程材料(Stanford University)