树

一、先搞懂：什么是「树」？

1. 直观理解

树是一种非线性的数据结构，长得和现实中的树一样：

有一个「根」，从根上长出「树枝」，树枝再分叉出更多小树枝，最后到「叶子」。
和数组、链表这种 “一条线” 的线性结构不同，树是 “一层一层分叉” 的结构。

2. 核心定义（抽象版）

树是由 n (n ≥ 1) 个节点组成的有限集合：

有且仅有一个特定的节点，称为根节点（Root）；
其余节点可分为 m (m ≥ 0) 个互不相交的有限集合，每个集合本身又是一棵树，称为根的子树（Subtree）。

二、基础术语：先把 “零件” 认全

以这棵简单的树为例（A 是根）：

     A
   /   \
  B     C
 / \
D   E

术语	解释	对应例子
根节点（Root）	树最顶层、没有父节点的节点	A
父节点（Parent）	有子节点的节点	A 是 B、C 的父节点；B 是 D、E 的父节点
子节点（Child）	某个节点下面直接连接的节点	B、C 是 A 的子节点；D、E 是 B 的子节点
叶子节点（Leaf）	没有子节点的节点	C、D、E
兄弟节点（Sibling）	同一个父节点的子节点	B 和 C 是兄弟；D 和 E 是兄弟
节点的度（Degree）	节点拥有的子节点个数	A 的度是 2；B 的度是 2；C 的度是 0
树的度	树中所有节点的度的最大值	这棵树的度是 2
节点的层次（Level）	根节点是第 1 层，往下依次 + 1	A 在第 1 层；B、C 在第 2 层；D、E 在第 3 层
树的深度 / 高度（Depth/Height）	树中节点的最大层次	这棵树的深度是 3
路径	从一个节点到另一个节点的节点序列	从 A 到 D 的路径是 A→B→D

三、最常见的树：二叉树（Binary Tree）

二叉树是树的 “基础款”，也是所有复杂树结构的起点，我们重点讲它。

1. 定义

每个节点最多只有 2 个子节点，分别称为「左子节点」和「右子节点」（顺序不能乱！）。

2. 二叉树的 5 种基本形态

空二叉树（一个节点都没有）
只有根节点
根节点只有左子树
根节点只有右子树
根节点同时有左、右子树

3. 两种特殊的二叉树

（1）满二叉树

定义：除了最后一层的叶子节点外，每一层的所有节点都有两个子节点；所有叶子节点都在同一层。
特点：节点数是 2^h - 1（h 是树的高度），比如高度为 3 的满二叉树，节点数是 2³-1=7。

推导过程

     A
   /   \
  B     C
 / \   / \
D   E F   G

（2）完全二叉树

定义：除了最后一层外，其他层的节点数都达到最大值；且最后一层的节点都靠左排列。
特点：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

     A
   /   \
  B     C
 / \   /
D   E F

四、二叉树的 3 种遍历方式（核心！）

遍历就是 “按某种顺序访问树的所有节点，且每个节点只访问一次”。二叉树有 3 种经典遍历，区别在于访问根节点的顺序。

以这棵树为例：

     A
   /   \
  B     C
 / \
D   E

1. 前序遍历（根 → 左 → 右）

访问根节点
前序遍历左子树
前序遍历右子树

遍历结果：A → B → D → E → C

2. 中序遍历（左 → 根 → 右）

中序遍历左子树
访问根节点
中序遍历右子树

遍历结果：D → B → E → A → C

3. 后序遍历（左 → 右 → 根）

后序遍历左子树
后序遍历右子树
访问根节点

遍历结果：D → E → B → C → A

五、进阶：二叉搜索树（BST）—— 让树能 “快速找东西”

普通二叉树只能存数据，而二叉搜索树（Binary Search Tree）是为了高效查找而生的。查找效率为 O (log n)

时间复杂度为O(最坏情况执行次数)

因为每层只查找一次所以层数为执行次数，也就是O(h)

左子树所有值 <当前节点，右子树所有值> 当前节点

查找原理：

1.永远从根节点开始；

2.每到一个节点，只判断大小，二选一：走左或走右；

3.每层只访问 1 个节点，不会遍历整棵树；

4.最坏情况：一直走到最底层叶子节点，一共走的步数 = 树的高度 h。退化为O (n)

1. 定义（核心规则）

对于树中的任意节点：

左子树的所有节点值 < 根节点值
右子树的所有节点值 > 根节点值
左右子树也必须满足这个规则

2. 例子

     5
   /   \
  3     7
 / \   / \
2   4 6   8

根节点是 5，左子树所有节点（2、3、4）都小于 5，右子树所有节点（6、7、8）都大于 5；
节点 3 的左子树 2 <3，右子树 4> 3，以此类推。

3. 中序遍历的特殊性质

二叉搜索树的中序遍历结果一定是升序的。比如上面的树，中序遍历结果是：2 → 3 → 4 → 5 → 6 → 7 → 8。

六、再进阶：平衡二叉树 —— 解决 BST 的 “退化问题”

1. BST 的致命缺陷

如果插入的数据是有序的（比如 1、2、3、4、5），BST 会退化成一条链表，查找效率从 O (log n) 变成 O (n)，失去了优势。

2. 平衡二叉树的核心思想

让树的左右子树高度差不超过 1，避免树变成 “斜树”，保证查找效率稳定在 O (log n)。

常见的平衡二叉树有：

AVL 树（最经典的平衡二叉树）
红黑树（实际工程中最常用，比如 C++ 的 map、Java 的 TreeMap 底层都是红黑树）

七、树的实际应用

树结构不是纸上谈兵，实际开发中到处都在用：

文件系统：电脑的文件夹就是典型的树结构，根目录下有多个子文件夹，子文件夹又可以继续嵌套。
数据库索引：MySQL 的 InnoDB 引擎用 B + 树做索引，大幅提升数据查询速度。
编译器：语法分析阶段会把代码转换成抽象语法树（AST），用来理解代码的结构。
前端 DOM：网页的 HTML 结构就是一棵 DOM 树，根节点是，下面嵌套、``等节点。
AI / 提示工程：你之前问的「思维树（ToT）」，就是把树结构的思想用到了大模型的推理上，模拟多路径探索和回溯。

八、小练习

用下面的树，写出它的前序、中序、后序遍历结果，看看你有没有掌握：

     1
   /   \
  2     3
 / \     \
4   5     6

（答案：前序1→2→4→5→3→6，中序4→2→5→1→3→6，后序4→5→2→6→3→1）