71 lines
3.8 KiB
Markdown
71 lines
3.8 KiB
Markdown
- 前
|
||
```
|
||
void Order(tree){
|
||
print(data);
|
||
Order(left);
|
||
Order(right);
|
||
}
|
||
```
|
||
|
||
- 中
|
||
```
|
||
void Order(tree){
|
||
Order(left);
|
||
print(data);
|
||
Order(right);
|
||
}
|
||
```
|
||
|
||
- 后
|
||
```
|
||
void Order(tree){
|
||
Order(left);
|
||
Order(right);
|
||
print(data);
|
||
}
|
||
```
|
||
|
||
|
||
### 1. 前序遍历 (Root-Left-Right)
|
||
|
||
- **复制二叉树：** 需要先创建当前根节点，再递归复制其左右子树。前序遍历天然符合这个过程。
|
||
|
||
- **获取前缀表达式：** 在表达式树中，前序遍历直接得到前缀表达式（波兰表达式），无需括号即可明确运算顺序，常用于某些计算器或编译器。
|
||
|
||
- **序列化二叉树：** 将树结构转化为字符串或字节流以便存储或传输。前序遍历序列化相对直观（常用`#`或`null`表示空节点）。
|
||
|
||
- **打印结构化文档/目录树：** 需要先打印当前目录/节点，再打印其子目录/子节点，形成缩进结构。
|
||
|
||
- **某些树形UI的渲染：** 有时需要先渲染父组件/节点，再递归渲染其子组件/节点。
|
||
|
||
|
||
### 2. 中序遍历 (Left-Root-Right)
|
||
|
||
- **二叉搜索树(BST)的排序输出：** **最重要的应用！** 对BST进行中序遍历，会以升序（从小到大）输出所有节点的值。这是BST的核心特性之一。
|
||
|
||
- **获取中缀表达式：** 在表达式树中，中序遍历得到中缀表达式（常见的数学表达式形式）。但需要注意，中序遍历本身不包含括号信息，需要额外处理运算符优先级。
|
||
|
||
- **查找BST中的第K小/大元素：** 利用中序遍历的有序性，可以在O(k)时间复杂度（平均）或O(n)（最坏）找到第k小的元素。优化方法（如Morris遍历或记录子树大小）可提高效率。
|
||
|
||
- **验证二叉搜索树：** 在中序遍历过程中，检查当前节点值是否**严格大于**前一个访问节点的值。如果不是，则不是有效的BST。
|
||
|
||
- **双向链表的转换：** 将BST原地转换成一个按节点值升序排序的双向链表，通常利用中序遍历修改节点指针实现。
|
||
|
||
|
||
### 3. 后序遍历 (Left-Right-Root)
|
||
|
||
- **删除二叉树：** 为了安全释放内存，必须先删除左右子树的所有节点，最后才删除根节点本身。后序遍历完美符合这个顺序。
|
||
|
||
- **计算节点的高度/深度：** 要计算一个节点的高度（到最深叶子节点的距离），需要先知道其左右子树的高度，取最大值再加1。后序遍历先访问子树，再访问根节点。
|
||
|
||
- **计算表达式树的值：** 需要先计算左右子树（子表达式）的值，才能用根节点的运算符对这两个结果进行运算。后序遍历直接得到后缀表达式（逆波兰表达式），非常适合用栈来高效计算。
|
||
|
||
- **获取后缀表达式：** 在表达式树中，后序遍历直接得到后缀表达式（逆波兰表达式），无需括号且易于用栈求值。
|
||
|
||
- **计算目录/子树大小：** 要计算一个目录（节点）的总大小（包含其所有子目录和文件），必须先计算其所有子目录的大小，然后加上自身文件的大小。后序遍历满足此需求。
|
||
|
||
- **判断树/子树的结构或属性：** 许多树的问题（如判断平衡二叉树、计算直径、查找最近公共祖先LCA）需要在递归到某个节点时，已经知道其左右子树的信息（如高度、是否存在目标节点、子树的结果等）。后序遍历提供了这种自底向上的信息传递方式。
|
||
|
||
- **释放树/图资源：** 类似于删除，需要先释放子节点资源，再释放父节点资源（如文件句柄、网络连接等）。
|
||
|
||
- **某些垃圾回收算法：** 标记-清除等算法在回收内存前，可能需要遍历对象引用图，后序遍历有助于处理依赖关系。 |