Markdown (or Textile), Liquid, HTML & CSS go in. Static sites come out ready for deployment.

binary tree traversal

前序遍历

前序遍历的顺序是根-左-右

思路是：

1. 先将根结点入栈

2. 出栈一个元素，将右节点和左节点依次入栈

3. 重复 2 的步骤

总结： 典型的递归数据结构，典型的用栈来简化操作的算法。

中序遍历

中序遍历的顺序是 左-根-右，根节点不是先输出，这就有一点点复杂了。

1. 根节点入栈

2. 判断有没有左节点，如果有，则入栈，直到叶子节点

3. 此时栈中保存的就是所有的左节点和根节点。 出栈，判断有没有右节点，有则入栈，继续执行 2 中序遍历一个二叉查找树（BST）的结果是一个有序数组。

   后序遍历

   左-右-根

层次遍历

层次遍历的关键点在于如何记录每一层次是否遍历完成， 我们可以用一个标识位来表式当前层的结束。

具体做法：

1. 根节点入队列， 并入队列一个特殊的标识位，此处是 null

2. 出队列

3. 判断是不是 null， 如果是则代表本层已经结束。我们再次判断是否当前队列为空，如果不为空继续入队一个 null，否则说明遍历已经完成，我们什么都不不用做

4. 如果不为 null，说明这一层还没完，则将其左右子树依次入队列。 （重复2, 3, 4)

双色标记法

我们知道垃圾回收算法中，有一种算法叫三色标记法。 即：

· 用白色表示尚未访问 · 灰色表示尚未完全访问子节点 · 黑色表示子节点全部访问 那么我们可以模仿其思想，使用双色标记法来统一三种遍历。

其核心思想如下：

· 使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。 · 如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。 · 如果遇到的节点为灰色，则将节点的值输出。