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)

后继节点