文档介绍：二叉树非递归遍历 收藏
 
从递归说起
void preOrder(TNode* root)
{
    if (root != NULL)
    {
        Visit(root);
        preOrder(root->left);
        preOrder(root->right);
    }
}
递归算法非常的简单。先访问跟节点,然后访问左节点,再访问右节点。如果不用递归,那该怎么做呢?仔细看一下递归程序,就会发现,其实每次都是走树的左分支(left),直到左子树为空,然后开始从递归的最深处返回,然后开始恢复递归现场,访问右子树。
其实过程很简单:一直往左走 root->left->left->left...->null,由于是先序遍历,因此一遇到节点,便需要立即访问;由于一直走到最左边后,需要逐步返回到父节点访问右节点,因此必须有一个措施能够对节点序列回溯。有两个办法:
:在访问途中将依次遇到的节点保存下来。由于节点出现次序与恢复次序是反序的,因此是一个先进后出结构,需要用栈。
使用栈记忆的实现有两个版本。第一个版本是模拟递归的实现效果,跟LX讨论的,第二个版本是直接模拟递归。
:通过指向父节点的指针来回溯(后来发现还要需要增加一个访问标志,来指示节点是否已经被访问,不知道可不可以不用标志直接实现回溯?想了一下,如果不用这个标志位,回溯的过程会繁琐很多。暂时没有更好的办法。)
(还有其他办法可以回溯么?)
这3个算法伪代码如下,没有测试过。
先序遍历伪代码:非递归版本,用栈实现,版本1
// 先序遍历伪代码:非递归版本,用栈实现,版本1 
void preOrder1(TNode* root)
{
    Stack S;
    while ((root != NULL) || !())
    {
        if (root != NULL)
        {
            Visit(root);
            (root);       // 先序就体现在这里了,先访问,再入栈 
            root = root->left; // 依次访问左子树 
        }
        else
        {
            root = ();     // 回溯至父亲节点 
            root = root->right;
        }
    }
}
preOrder1每次都将遇到的节点压入栈,当左子树遍历完毕后才从栈中弹出最后一个访问的节点,访问其右子树。在同一层中,不可能同时有两个节点压入栈,因此栈的大小空间为O(h),h为二叉树高度。时间方面,每个节点都被压入栈一次,弹出栈一次,访问一次,复杂度为O(n)
先序遍历伪代码:非递归版本,用栈实现,版本2
// 先序遍历伪代码:非递归版本,用栈实现,版本2 
void preOrder2(TNode* root)
{
    if ( root != NULL)
    {
        Sta