1. 遍历
- 线性数据结构的遍历方式：
正序遍历
逆序遍历- 二叉树的遍历方式：
前序遍历（Preorder Traversal）
中序遍历（Inorder Traversal）
后序遍历（Postorder Traversal）
层序遍历（Level Order Traversal）
(1) 前序遍历（Preorder Traversal）
访问顺序：
- 根节点、前序遍历左子树、前序遍历右子树
7、4、2、1、3、5、9、8、11、10、12
前序遍历
前序遍历 - 非递归
前序遍历 - 非递归
(2) 中序遍历（Inorder Traversal）
访问顺序：
- 中序遍历左子树、根节点、中序遍历右子树
1、2、3、4、5、7、8、9、10、11、12- 中序遍历右子树、根节点、中序遍历左子树
12、11、10、9、8、7、5、4、3、2、1- 二叉搜索树的中序遍历结果是 升序 或者 降序 的
中序遍历
中序遍历 - 非递归
(3) 后序遍历（Postorder Traversal）
访问顺序：
- 后序遍历左子树、后序遍历右子树、根节点
1、3、2、5、4、8、10、12、11、9、7
后序遍历
后序遍历 - 非递归
(4) 层序遍历（Level Order Traversal）
访问顺序：
- 从上到下、从左到右 一次访问每一个节点
7、4、9、2、5、8、11、1、3、10、12
层序遍历
层序遍历 - 非递归
2. 遍历的应用
(1) 原理
- 前序遍历
树状结构展示- 中序遍历
二叉搜索树的中序遍历 按升序或降序 处理节点- 后序遍历
适用于一些先子后父的操作- 层序遍历
计算二叉树的高度
判断一棵树是否为完全二叉树
(2) 四则运算
- 前缀表达式：波兰表达式
- 中缀表达式：
- 后缀表达式：逆波兰表达式
四则运算
(3) 表达式树
表达式树
表达式 A / B + C * D - E 组成二叉树
- 前序遍历：- + / A B * C D E ------ 前缀表达式：波兰表达式
- 中序遍历：A / B + C * D - E ------ 中缀表达式：波兰表达式
- 后序遍历：A B / C D * + E - ------ 后缀表达式：逆波兰表达式
(4) 重构二叉树
保证重构出唯一的一棵二叉树
- 前序遍历 + 中序遍历
- 后序遍历 + 中序遍历
(5) 判断一棵树是否为完全二叉树
判断一棵树是否为完全二叉树
3. 前驱后继
(1) 前驱结点(predecessor)
前驱结点
(2) 后继节点(successor)
后继节点
