二、非递归深度优先周游二叉树

栈是实现递归的最常用的结构，利用一个栈来记下尚待周游的结点或子树，以备以后访问，可以将递归的深度优先周游改为非递归的算法。

1、非递归前序周游：遇到一个结点，就访问该结点，并把此结点推入栈中，然后下降去周游它的左子树。周游完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去周游该结点的右子树结构。

2、非递归中序周游：遇到一个结点，就把它推入栈中，并去周游它的左子树。周游完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去周游该结点的右子树。

3、非递归后序周游：遇到一个结点，把它推入栈中，周游它的左子树。周游结束后，还不能马上访问处于栈顶的该结点，而是要再按照它的右链接结构指示的地址去周游该结点的右子树。周游遍右子树后才能从栈顶托出该结点并访问之。另外，需要给栈中的每个元素加上一个特征位，以便当从栈顶托出一个结点时区别是从栈顶元素左边回来的(则要继续周游右子树)，还是从右边回来的(该结点的左、右子树均已周游)。特征为Left表示已进入该结点的左子树，将从左边回来；特征为Right表示已进入该结点的右子树，将从右边回来。

4、简洁的非递归前序周游：遇到一个结点，就访问该结点，并把此结点的非空右结点推入栈中，然后下降去周游它的左子树。周游完左子树后，从栈顶托出一个结点，并按照它的右链接指示的地址再去周游该结点的右子树结构。