二叉树遍历非递归算法

递归算法非常的简单。先访问跟节点，然后访问左节点，再访问右节点。如果不用递归，那该怎么做呢？仔细

一.先序遍历

　　看一下递归程序，就会发现，其实每次都是走树的左分支(left)，直到左子树为空，然后开始从递归的最深处返回，然后开始恢复递归现场，访问右子树。

由于一直走到最左边后，需要逐步返回到父节点访问右节点，因此必须有一个措施能够对节点序列回溯。

　　可以用栈记忆：在访问途中将依次遇到的节点保存下来。由于节点出现次序与恢复次序是反序的，因此是一个先

进后出结构，需要用栈；还可以节点增加指向父节点的指针。 

　　

二.中序遍历

三.后序遍历

　　不写了……

四.层次遍历