树的基础知识详解
树是一种非线性数据结构，由节点和连接节点的边组成，具有分层关系。它在计算机科学中应用广泛，例如文件系统、DOM 树、编译器语法树、数据库索引等。
一、树的定义与术语
定义：树是 n（n≥0）个节点的有限集合。当 n=0 时，称为空树。在任意一棵非空树中：
- 有且仅有一个特定的称为根（root）的节点。
- 其余节点可分为 m（m≥0）个互不相交的有限集合 T₁, T₂, …, Tm，每个集合本身又是一棵树，称为根的子树（subtree）。
基本术语：
- 节点：包含数据元素及若干指向其子树的分支。
- 节点的度：一个节点拥有的子树数（即子节点个数）。
- 叶子节点：度为 0 的节点（没有子节点）。
- 分支节点：度不为 0 的节点。
- 树的度：树内各节点的度的最大值。
- 孩子与双亲：节点的子树的根称为该节点的孩子，该节点称为孩子的双亲。
- 兄弟：同一个双亲的孩子之间互称兄弟。
- 祖先与子孙：从根到某节点路径上的所有节点都是该节点的祖先；某节点子树中的任一节点都是该节点的子孙。
- 层次：根为第一层，根的孩子为第二层，以此类推。
- 深度：树中节点的最大层次数。
- 高度：从叶子节点向上数到根节点的最大层数（有些定义与深度相同，通常可互换）。
- 森林：m（m≥0）棵互不相交的树的集合。
二、树的分类
根据节点分支数量和结构特性，树可分为多种类型。
1. 二叉树（Binary Tree）
每个节点最多有两个子节点，分别称为左孩子和右孩子。二叉树是算法题中最常见的树结构。
特殊形态：
- 满二叉树：所有分支节点都有左右孩子，且叶子节点都在同一层。节点数 = 2^k - 1（k 为层数）。
- 完全二叉树：除了最后一层，其余层都是满的，且最后一层的节点都靠左排列。可用数组高效存储。
- 平衡二叉树：左右子树高度差不超过 1（如 AVL 树），确保查找效率 O(log n)。
- 二叉搜索树（BST）：左子树所有节点值 < 根节点值 < 右子树所有节点值，且左右子树也是 BST。
2. N 叉树（N-ary Tree）
每个节点可以有多个子节点，如文件系统、DOM 树、Trie 树等。
3. 其他特殊树
- 堆（Heap）：一种完全二叉树，常用于实现优先队列。最大堆：根节点最大；最小堆：根节点最小。
- Trie 树（前缀树）：用于高效存储和检索字符串，每个节点代表一个字符路径。
- 并查集（Union-Find）：森林结构，用于处理不相交集合的合并与查询。
三、二叉树的存储方式
1. 链式存储（最常用）
每个节点包含数据域和左右指针。
javascript
function TreeNode(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}2. 顺序存储（数组）
适合完全二叉树。根节点下标为 1（或 0），节点 i 的左孩子为 2i，右孩子为 2i+1（若下标从 1 开始）。这种存储方式在堆排序中常用。
四、二叉树的遍历
遍历是树操作的基础，按访问根节点的顺序分为深度优先遍历（DFS）和广度优先遍历（BFS）。
1. 深度优先遍历（DFS）
利用递归或栈实现，分为前序、中序、后序。
前序遍历（根左右）：先访问根节点，再遍历左子树，最后右子树。 中序遍历（左根右）：先遍历左子树，再访问根节点，最后右子树。（对于 BST，中序遍历得到有序序列） 后序遍历（左右根）：先遍历左子树，再右子树，最后访问根节点。（常用于释放树节点）
递归实现（以中序为例）：
javascript
function inorderTraversal(root) {
const res = [];
function inorder(node) {
if (!node) return;
inorder(node.left);
res.push(node.val);
inorder(node.right);
}
inorder(root);
return res;
}迭代实现（以中序为例）：
javascript
function inorderTraversal(root) {
const res = [];
const stack = [];
let cur = root;
while (cur || stack.length) {
while (cur) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
res.push(cur.val);
cur = cur.right;
}
return res;
}2. 广度优先遍历（BFS）
利用队列实现，从上到下、从左到右逐层访问节点。又称层序遍历。
层序遍历（输出一维数组）：
javascript
function levelOrder(root) {
if (!root) return [];
const res = [];
const queue = [root];
while (queue.length) {
const node = queue.shift();
res.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return res;
}按层分组输出：
javascript
function levelOrderGrouped(root) {
if (!root) return [];
const res = [];
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
res.push(level);
}
return res;
}3. 遍历复杂度
- 时间复杂度：O(n)，每个节点访问一次。
- 空间复杂度：
- 递归：最坏 O(n)（树退化成链表），平均 O(log n)。
- 迭代：栈或队列最多存储 O(n) 个节点。
五、二叉搜索树（BST）
BST 是一种特殊的二叉树，满足：
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 左右子树也是 BST
1. 查找
从根开始比较，小于当前节点则向左，大于则向右，等于则返回。
javascript
function searchBST(root, val) {
if (!root || root.val === val) return root;
return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}2. 插入
类似查找，找到空位置插入新节点。
javascript
function insertIntoBST(root, val) {
if (!root) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}3. 删除
较复杂，需考虑三种情况：
- 叶子节点：直接删除。
- 有一个子节点：用子节点替换。
- 有两个子节点：找到右子树的最小节点（或左子树的最大节点）替换当前节点，然后删除该最小节点。
javascript
function deleteNode(root, val) {
if (!root) return null;
if (val < root.val) {
root.left = deleteNode(root.left, val);
} else if (val > root.val) {
root.right = deleteNode(root.right, val);
} else {
// 找到待删节点
if (!root.left && !root.right) return null; // 叶子
if (!root.left) return root.right; // 只有右子
if (!root.right) return root.left; // 只有左子
// 有两个子节点：找右子树最小节点
let minNode = root.right;
while (minNode.left) minNode = minNode.left;
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
return root;
}4. BST 的复杂度
- 平均：O(log n)
- 最坏（退化成链表）：O(n)
六、平衡二叉树
为了解决 BST 在最坏情况下退化为链表的问题，引入了平衡二叉树，保证树的高度始终为 O(log n)。常见的平衡树有：
- AVL 树：严格平衡，左右子树高度差不超过 1，通过旋转保持平衡。
- 红黑树：近似平衡，通过颜色和旋转规则保证最长路径不超过最短路径的两倍，广泛应用于 C++ STL map、Java TreeMap、Linux 内核等。
平衡树在面试中较少要求手写实现，但理解其思想有助于分析复杂题。
七、树的其他应用
1. 堆（优先队列）
堆是完全二叉树，常用数组存储。分为最大堆和最小堆，支持 O(log n) 的插入和删除堆顶操作。堆排序、Top K 问题、Dijkstra 算法等都会用到。
JavaScript 中无原生堆，需手动实现。
2. Trie 树（前缀树）
用于高效存储和查询字符串集合，每个节点包含一个字符映射数组或对象，以及一个结束标记。适用于自动补全、拼写检查等。
3. 并查集
处理动态连通性问题，如判断两个元素是否在同一集合、合并集合等。底层为森林，用数组表示父节点关系。
八、树的常见算法思想
- 递归：树的定义本身就是递归的，因此绝大多数树问题都可以用递归解决。
- 回溯：在路径问题中，需要记录路径并在递归返回时撤销选择。
- 分治：将问题分解为左右子树分别解决，再合并结果。
- 动态规划：树形 DP，如监控二叉树、打家劫舍 III。
九、树的复杂度分析总结
| 操作 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 遍历 | O(n) | O(n) |
| BST 查找 | O(log n) | O(n) |
| BST 插入 | O(log n) | O(n) |
| BST 删除 | O(log n) | O(n) |
| 平衡树查找/插入/删除 | O(log n) | O(log n) |
| 堆插入/删除 | O(log n) | O(log n) |
空间复杂度取决于递归深度或显式栈/队列大小，最坏 O(n)。
十、JavaScript 中树的常见坑点
- 递归溢出：当树深度很大时（如 10^5），递归可能导致栈溢出，此时应改用迭代。
- 引用类型：在 JavaScript 中，对象是引用传递，修改节点属性会直接影响原树。
- null 判断：操作树前务必判断节点是否为 null，避免访问 null 的属性。
- 拷贝路径：在回溯题中，向结果集添加路径时需深拷贝数组（
[...path]），否则后续修改会影响已保存的结果。