【Day14】[资料结构]-二元树走访Binary Tree Traversal

二元树走访或称二元树遍历，简单来说就是走访树中各节点，转化为线性关系。

主要分成两种策略方式

• 深度优先搜寻（Depth-first Search，DFS）
  从根节点出发，选择某一子树并以垂直方向由上到下处理，将其子节点访问完後，再选择另一子树走访。
• 广度优先搜寻（Breath-first Search，BFS）
  从根节点出发，以水平方向由左到右走访，将同阶层的兄弟节点访问完之後，再走访下一阶层的节点。

深度优先搜寻 DFS

假设根结点为N、左子树为L、右子树为R

• 前序走访(Pre-order Traversal): NLR, 根节点 → 左子树 → 右子树
• 中序走访(In-order Traversal): LNR, 左子树 → 根节点 → 右子树
• 後序走访(Post-order Traversal): LRN, 左子树 → 右子树 → 根节点

广度优先搜寻 BFS

• 层序走访(Level-order Traversal): 1234567

以下图为例

1. 前序走访： 顺序是根节点、左子节点、右子节点。
   [1, 2, 4, 8, 9, 5, 3, 6, 10, 11, 7]
2. 中序走访： 顺序是左子节点、根节点、右子节点。
   [8, 4, 9, 2, 5, 1, 10, 6, 11, 3, 7]
3. 後序走访历： 顺序是左子节点、右子节点、根节点。
   [8, 9, 4, 5, 2, 10, 11, 6, 7, 3, 1]
4. 层序走访： 顺序是由根节点一层一层往下，由左往右。
   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]