一、递归遍历：

1、先序遍历：

---

2、中序遍历：

---

3、后续遍历：

总结规律：

二、非递归遍历：利用栈来实现

非递归算法实现的基本思路：使用堆栈

【1】中序遍历非递归遍历算法:

1、遇到一个结点，就把它压栈，并去遍历它的左子树；

2、当左子树遍历结束后，从栈顶弹出这个结点并访问它；

3、然后按其右指针再去中序遍历该结点的右子树。

---

【2】先序遍历的非递归遍历算法：

只需把输出语句调换到第一次访问元素的位置即可

【3】后序遍历的非递归遍历算法：

参考文章1
参考文章2
参考文章3

• 后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。

• 对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问， 因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就 保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。
  

  
  该双栈法较为简单明了，来自参考文章2

三、层序遍历：利用队列实现

按照树的层级进行遍历，因此每次要把其左右孩子记录下来