什么是树结构？
📖 基本定义
树（Tree）是一种重要的非线性数据结构，由n(n≥0)个有限节点组成的具有层次关系的集合。
树结构像自然界中的树一样，有根、枝、叶，但在计算机科学中，树是倒置的——根在上，叶在下。
✨ 核心特点
• 每个节点有零个或多个子节点
• 没有父节点的节点称为根节点
• 每个非根节点有且只有一个父节点
• 除根节点外，每个子节点可分为多个不相交的子树
🎯 为什么重要
树结构广泛应用于：
• 文件系统的目录结构
• 数据库索引（B树、B+树）
• HTML/XML文档解析（DOM树）
• 编译器语法分析（AST）
💡 知识要点：
树结构的核心优势在于其层次性和递归性，这使得许多复杂问题可以通过分而治之的策略高效解决。树的搜索、插入、删除操作在平衡状态下的时间复杂度为 O(log n)。
核心术语解析
根节点 (Root)
树的最顶端节点，没有父节点，是整棵树的起点。每棵树只有一个根节点。
叶节点 (Leaf)
没有子节点的节点，也称为终端节点，是树的末端。
内部节点 (Internal)
至少有一个子节点的节点，即非叶子节点，也称为分支节点。
父节点 (Parent)
有子节点的节点称为其子节点的父节点，体现了树的层级关系。
子节点 (Child)
一个节点的直接下级节点，一个父节点可以有多个子节点。
兄弟节点 (Sibling)
具有相同父节点的节点之间互称为兄弟节点。
深度 (Depth)
从根节点到该节点的边数，根节点的深度为0。
高度 (Height)
从该节点到最远叶节点的边数，叶节点高度为0，树的高度即根节点的高度。
层 (Level)
根节点在第1层，其子节点在第2层，依此类推。层数 = 深度 + 1。
度 (Degree)
一个节点的子节点数量称为该节点的度，树的度是所有节点度的最大值。
子树 (Subtree)
由某节点及其所有后代节点组成的树结构，体现了树的递归特性。
路径 (Path)
从一个节点到另一个节点经过的节点序列，路径长度为经过的边数。
常见树的类型
二叉树 (Binary Tree)
最基础也是最重要的树结构
📌 特点
- 每个节点最多有两个子节点
- 子节点有左右之分，不能颠倒
- 即使只有一个子节点也要区分左右
🔧 变体
- 满二叉树：所有叶子在同一层，每个非叶子节点都有两个子节点
- 完全二叉树：除最后一层外全满，最后一层从左到右连续
二叉搜索树 (BST)
高效查找的利器
📌 特点
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 左右子树也是二叉搜索树
⚡ 性能
- 平均查找时间：O(log n)
- 最坏情况（退化成链表）：O(n)
- 中序遍历得到有序序列
AVL树
最早的自平衡二叉搜索树
📌 特点
- 每个节点的左右子树高度差 ≤ 1
- 通过旋转操作保持平衡
- 查找效率始终为 O(log n)
🔄 旋转操作
- LL旋转：右旋转
- RR旋转：左旋转
- LR旋转：先左旋后右旋
- RL旋转：先右旋后左旋
红黑树 (Red-Black Tree)
工业级应用的首选
📌 特点
- 节点非红即黑
- 根节点和叶子节点(NIL)是黑色
- 红色节点的子节点必须是黑色
- 从任一节点到叶子的路径包含相同数量的黑色节点
💼 应用
- Java TreeMap/TreeSet
- C++ STL map/set
- Linux内核进程调度
B树 (B-Tree)
磁盘存储的最佳选择
📌 特点
- 多路平衡查找树
- 一个节点可以有多个key和子节点
- 所有叶子节点在同一层
- 适合读写大块数据的存储系统
💼 应用
- 数据库索引
- 文件系统
- 磁盘块管理
堆 (Heap)
优先队列的完美实现
📌 特点
- 完全二叉树结构
- 最大堆：父节点 ≥ 子节点
- 最小堆：父节点 ≤ 子节点
- 可以用数组高效实现
💼 应用
- 优先队列
- 堆排序算法
- Top K 问题
- 任务调度系统
树的遍历算法
📖 遍历概念：
树的遍历是指按照某种顺序访问树中的每个节点，且每个节点仅被访问一次。遍历是树操作的基础，理解不同遍历方式对于解决树相关问题至关重要。
🎮 遍历可视化演示
遍历顺序
前序遍历 (Pre-order)
访问顺序：根 → 左 → 右
应用场景：复制树结构、前缀表达式
JavaScript - 四种遍历实现
// 前序遍历 (Pre-order): 根 → 左 → 右 function preorderTraversal(root) { if (!root) return []; return [root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right)]; } // 中序遍历 (In-order): 左 → 根 → 右 function inorderTraversal(root) { if (!root) return []; return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]; } // 后序遍历 (Post-order): 左 → 右 → 根 function postorderTraversal(root) { if (!root) return []; return [...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val]; } // 层序遍历 (Level-order): 逐层从左到右 function levelOrderTraversal(root) { if (!root) return []; const result = [], queue = [root]; while (queue.length) { const node = queue.shift(); result.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } return result; }
交互式树结构演示
动态树可视化
点击节点选中，然后可以添加子节点、删除节点或编辑节点名称。支持拖拽和缩放。
时间复杂度对比
| 数据结构 | 查找 | 插入 | 删除 | 空间复杂度 |
|---|---|---|---|---|
| 二叉搜索树 (平均) | O(log n) | O(log n) | O(log n) | O(n) |
| 二叉搜索树 (最坏) | O(n) | O(n) | O(n) | O(n) |
| AVL树 | O(log n) | O(log n) | O(log n) | O(n) |
| 红黑树 | O(log n) | O(log n) | O(log n) | O(n) |
| B树 | O(log n) | O(log n) | O(log n) | O(n) |
| 堆 | O(n) | O(log n) | O(log n) | O(n) |
| 字典树 (Trie) | O(m)* | O(m)* | O(m)* | O(字符集大小 × m × n) |
* m 表示字符串长度
实际应用场景
文件系统
操作系统使用树结构组织文件和目录，实现层级管理
数据库索引
B树和B+树广泛用于数据库索引，加速数据查询
DOM结构
HTML文档被解析为DOM树，支持网页元素的访问和操作
搜索建议
Trie树用于实现搜索引擎的自动补全和拼写检查
网络路由
路由器使用树结构存储和查找IP路由信息
游戏AI
决策树和行为树用于游戏中NPC的智能行为
压缩算法
哈夫曼树用于数据压缩，如ZIP和JPEG格式
编译器
抽象语法树(AST)用于代码解析和优化