Tree树到底是怎么组织数据的
树是一种比数组和链表更有层次的数据结构，文件目录、组织架构、DOM、数据库索引都能看到它的影子。这篇从根节点、父子关系和高度讲起，配图说明二叉树、搜索树、堆和树的遍历，再聊聊它和链表的区别以及常见优缺点。
前面我们已经聊过 Array 数组为什么查得快改得慢和 LinkedList 链表怎么查和改。
数组是一排连续的数据，链表是一串靠指针连接起来的数据。
但现实里的很多关系并不是一条线。
文件夹里面还有文件夹，公司部门下面还有小组，网页节点下面还有子节点。
这类一层套一层的关系，用线性表描述就有点别扭了。
于是我们需要一种更有层次的数据结构：Tree，树。
树的核心并不复杂。
找一个根节点，下面挂子节点，子节点还可以继续挂自己的子节点，最后形成一棵有层次的结构。
这篇先把树的基本概念讲清，再看二叉树、二叉搜索树、堆和遍历。
树到底是什么
树是一种非线性数据结构。
它由一组节点组成，节点之间通过边连接，并且通常从一个根节点向下展开。
根节点
A
/ \
B C
/ \ \
D E F
/ \
G H
这张图里：
- A 是根节点
- B 和 C 是 A 的子节点
- A 是 B 和 C 的父节点
- D、E、F、G、H 是更下层的节点
- 没有子节点的 D、F、G、H 叫叶子节点
树和链表一样，也可以用指针或引用连接节点。
区别是链表节点通常只有一个后继方向，而树节点可以拥有多个子节点。
树的基本术语
理解树时，经常会遇到这些词：
A ← 根节点
/ \
B C
/ \
D E
- 节点：树中的一个数据单元
- 边：连接两个节点的关系
- 根节点：没有父节点的节点
- 父节点：直接连接在上方的节点
- 子节点：直接连接在下方的节点
- 兄弟节点：拥有同一个父节点的节点
- 叶子节点：没有子节点的节点
- 路径：从一个节点沿边走到另一个节点的路线
- 子树：某个节点以及它下面的全部节点
比如以 B 为根的子树，就是 B、D、E 组成的那一部分。
## 深度、高度和层
从根节点向下数，可以描述节点所在的层。
```text
第 0 层： A
/ \
第 1 层： B C
/ \
第 2 层： D E
常见概念有：
- 深度：从根节点走到当前节点经过的边数
- 高度：从当前节点走到最深叶子节点的边数
- 树高：根节点的高度
- 层数：节点所在的层级
树高很重要。
很多树的查询、插入和删除复杂度，都会和从根走到目标节点的路径长度有关。
树越平衡，高度越低，操作通常越快。
树和图有什么区别
树可以看成一种特殊的图，但它比普通图多一些约束。
树：
A
/ \
B C
/ \
D E
一棵树通常具备这些特点：
- 有一个根节点
- 节点之间没有环
- 除根节点外，每个节点通常只有一个父节点
- 任意两个节点之间通常只有一条唯一路径
- 有 n 个节点时，边通常是 n - 1 条
普通图则可以有环，也可以有多个方向和多条路径：
A ---- B
| |
└── C ─┘
图适合描述道路、社交关系和网络连接。
树适合描述目录、组织、分类和层级关系。
二叉树怎么回事
二叉树是最常见的一类树。
它的约束很简单：每个节点最多拥有两个子节点，分别叫左子节点和右子节点。
1
/ \
2 3
/ \ / \
4 5 6 7
节点可以只有左孩子，也可以只有右孩子，也可以一个孩子都没有。
class TreeNode<T> {
T value;
TreeNode<T> left;
TreeNode<T> right;
}
二叉树的每个节点只保存两个子引用，结构比较规整，很多搜索和排序算法都以它为基础。
满二叉树
满二叉树的每一层都填满了节点。
1
┌────┴────┐
2 3
┌──┴──┐ ┌──┴──┐
4 5 6 7
如果根节点所在层从 0 开始，高度为 h 的满二叉树节点数量是：
2^(h + 1) - 1
完全二叉树
完全二叉树要求除最后一层外，其余层全部填满，最后一层的节点从左到右排列。
1
/ \
2 3
/ \ /
4 5 6
完全二叉树适合用数组保存，因为节点的父子下标可以通过公式计算。
如果数组下标从 1 开始：
父节点下标：i / 2
左孩子下标：2 * i
右孩子下标：2 * i + 1
这就是堆通常使用数组而不是指针节点的原因。
二叉搜索树
二叉搜索树，简称 BST，在二叉树基础上增加了排序规则：
- 左子树的值小于当前节点
- 右子树的值大于当前节点
- 每棵子树也都满足这个规则
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
查找 7 时，可以这样走：
7 < 8 -> 往左
7 > 3 -> 往右
7 > 6 -> 往右
找到 7
如果树比较平衡，每次比较都能排除一部分节点，查找平均可以接近 O(log n)。
BST 为什么可能退化
如果插入的数据本身已经有序：
依次插入：1、2、3、4、5
结果：
1
\
2
\
3
\
4
\
5
这棵树已经不像树了，更像一条链表。
此时查找复杂度从 O(log n) 退化成 O(n)。
所以实际工程中通常需要 AVL 树、红黑树等自平衡二叉搜索树，让树高保持在合理范围。
Java 的 TreeMap 和 TreeSet 就使用了红黑树思想。
BST 的插入和删除
插入一个新值时，从根节点开始比较，大于当前节点就往右，小于当前节点就往左，直到找到空位置。
插入 5：
8
/ \
3 10
/ \
1 6
/ \
4 7
5 < 8 -> 左
5 > 3 -> 右
5 < 6 -> 左
5 > 4 -> 右，插入到这里
删除则复杂一些：
- 删除叶子节点：直接删除
- 删除只有一个孩子的节点：让孩子顶上来
- 删除有两个孩子的节点：用后继或前驱替换，再删除那个节点
树结构的难点往往不在查找，而在删除后如何保持排序规则。
树的遍历方式
树不像数组那样天然只有从前到后的一个方向。
我们需要定义遍历顺序。
对二叉树来说，最常见的是前序、中序、后序和层序遍历。
A
/ \
B C
/ \ / \
D E F G
前序遍历
顺序是：根、左子树、右子树。
A -> B -> D -> E -> C -> F -> G
前序适合先处理父节点，再处理子节点的场景。
中序遍历
顺序是：左子树、根、右子树。
D -> B -> E -> A -> F -> C -> G
对二叉搜索树进行中序遍历，可以得到从小到大的有序序列。
这是 BST 最有用的性质之一。
后序遍历
顺序是：左子树、右子树、根。
D -> E -> B -> F -> G -> C -> A
后序适合先处理子节点，再处理父节点的场景，例如删除目录、计算子树大小。
层序遍历
层序遍历按层从上到下，通常使用队列实现：
第 0 层：A
第 1 层：B C
第 2 层：D E F G
结果：A -> B -> C -> D -> E -> F -> G
代码思路是：取出一个节点，把它的子节点加入队列，然后继续取下一个。
队列：A
取出 A，加入 B、C
队列：B、C
取出 B，加入 D、E
队列：C、D、E
继续处理
递归和栈怎么遍历
树的递归遍历代码通常很短：
void preorder(TreeNode<Integer> node) {
if (node == null) {
return;
}
visit(node.value);
preorder(node.left);
preorder(node.right);
}
递归其实是把访问路径放进了调用栈。
树太深时，递归也可能造成栈溢出。
这时可以手动使用栈，把递归过程改写成迭代。
递归：系统调用栈帮我们保存待处理节点
迭代：自己创建 Stack 保存待处理节点
层序遍历则天然适合队列。
深度优先：栈或递归
广度优先：队列
这也是树和栈、队列之间经常一起出现的原因。
堆也是一棵树
堆通常是一棵完全二叉树，但它的排序规则和二叉搜索树不同。
小顶堆要求每个父节点都不大于子节点：
1
/ \
3 2
/ \ / \
7 5 8 4
根节点永远是最小值。
大顶堆则相反，根节点永远是最大值。
堆最常见的用途是优先队列：
加入任务 -> 放到末尾 -> 向上调整
取出优先任务 -> 取走根节点 -> 末尾元素补到根 -> 向下调整
因为完全二叉树可以用数组表示，堆通常不需要节点指针。
这也说明一个问题：树不一定都用指针实现，具体要看树的形状和操作目标。
树的优点和缺点
树的优点
树的优势主要来自层级结构：
- 能表达父子、上下级和分类关系
- 适合递归处理子树
- BST 可以支持有序查找
- 堆可以快速获取最大值或最小值
- 平衡树能把搜索控制在 O(log n)
- 目录、DOM、索引等业务模型都很自然
树的缺点
树也不是万能结构：
- 节点关系比数组和链表复杂
- 指针或引用会带来额外内存开销
- 不平衡时，搜索树可能退化成链表
- 插入删除需要维护结构约束
- 递归遍历过深时可能栈溢出
- 并发修改树结构时需要额外同步
树的性能很依赖高度。
一棵平衡树和一棵退化树，名字都叫树，实际复杂度可能完全不同。
树和线性结构怎么选
可以先按数据关系选择：
数据是一条顺序队列？
└── Array / LinkedList
数据有父子层级？
└── Tree
数据需要多条路径和复杂连接？
└── Graph
再根据操作选择树的具体类型：
- 需要按层级展示：普通树
- 需要左右子树递归：二叉树
- 需要有序查找：二叉搜索树或平衡树
- 需要快速取最大/最小值：堆
- 需要前缀搜索：Trie 字典树
- 需要数据库磁盘索引：B+Tree 等多路搜索树
之前的 MySQL B+Tree 文章讲的是数据库索引为什么选择多路树结构。
那是树在磁盘和数据库场景下的具体应用，不是普通二叉树的简单放大版。
小结
Tree 树的核心是节点和层级关系。
从根节点出发，节点通过边连接成父子结构，子节点还可以继续形成子树。
常见的树形结构包括：
- 二叉树：每个节点最多两个孩子
- 二叉搜索树：左小右大，支持有序查找
- 平衡树：控制树高，避免退化
- 堆：根节点保持最大值或最小值
- B+Tree：常用于数据库和磁盘索引
树的遍历也要记住：
- 前序：根、左、右
- 中序：左、根、右
- 后序：左、右、根
- 层序：按层从上到下
一句话总结：数组和链表适合描述一条线，树适合描述一层层的关系。
选择树时别只看名字，先看树高、节点关系和核心操作，再决定使用普通树、搜索树、堆，还是更专业的平衡树和 B+Tree。