二叉树的各种遍历实现伪代码

本文的copyleft归[e-mail]所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。
作者：[e-mail]
博客：linuxfocus.blog.chinaunix.net 

最近需要复习一下基础算法，今天先来个二叉树的几种遍历方式的伪代码吧。

其中每种遍历方式都分为递归和非递归两种。

下面的代码我没有进行优化，可能代码有些冗余，不够简洁。因为没有真正的进行严格的测试，只是在纸上画了话，走了一下流程，欢迎大家指正错误。在代码中使用access作为访问节点数据的方式。其实最好的方法是将access作为类型为函数指针的参数，但是今天只为了温习一下实现，而不是真正的去写代码。就按照简单的来了。

对于非递归的实现，在上学的时候，当时并没有真正理解为什么要这样实现，来消除递归。现在我会把将递归转为非递归的过程描述得清楚一些。

1. 先序遍历：先访问根节点，然后遍历左子树，最后遍历右子树

a) 递归算法

void preorder_traverse(const struct bi_tree *tree)
{
    if (tree) {
        /* 访问根节点*/
        access(tree->data);

        if (tree->left) {
            /* 访问左节点 */
            preorder_traverse(tree->left);
        }

        if (tree->right) {
            /* 访问右节点 */
            preorder_traverse(tree->right);
        }
    }
}

递归实现太简单了，而且非常清晰，便于理解。

b) 非递归算法

void preorder_traverse(const struct bi_tree *tree)
{
    /*
    为什么要选择用栈呢。
    当我们遍历先序遍历二叉树时，按照先序的定义，先根节点，然后左节点，然后在右节点。
    这样当按照不断地访问左节点而向下时，为了以后打印右节点，所以需要保存右节点。
    之所以选择栈保存，因为打印右节点顺序与栈的特性先进后出相符，所以选择栈来保存右节点。

     后面的其他遍历方式，同样因为上面这个原因选择栈作为非递归遍历的一个保存方式。

    */
    struct stack s;

    init_stack(&s);

    const struct node *n = tree;

    while (n) {
        /* 访问节点 */
        access(n->data);

         

         /* 该节点有左子节点，需要不断的往下遍历 */

        while (n->left) {
            /* 有右节点，那么将右节点压栈 */
            if (n->right) {
                s.push(n->right);
            }

            /* 移到左节点 */
            n = n->left;
            /* 访问该节点，在这里也可看作新的根节点 */
            access(n->data);
        }

       

         /* 开始访问右节点 */

         if (n->right) {

             /* 移到右节点 */

             n = n->right;

         }

         else {

             /* 需要弹出上一个保存的右节点 */

             n = s.pop();

         }

    }
}

2. 中序遍历：先遍历左子树，然后根节点，最后是右子树

a) 递归算法

void midorder_traverse(const struct bi_tree *tree)
{
    if (tree->left) {
        midorder_traverse(tree->left);
    }
    access(tree->data);
    if (tree->right) {
        midorder_traverse(tree->right);
    }
}

递归实现就是简单啊

b) 非递归算法

void midorder_traverse(const struct bi_tree *tree)
{
    struct stack s;

    init_stack(&s);

    const struct node *n = tree;

    while (n) {

         /* 不断的沿左节点向下走 */

        while (n->left) {
            s.push(n);
            n = n->left;
        }

          

         /* 访问节点*/

        access(n->data);

         

         /* 弹出父节点 */

        while (n = s.pop()) {
            access(n->data)
            if (n->right) {
                /* 如果父节点有右节点，那么需要再次检查该右节点的左节点*/
                break;
            }
            /* 没有右节点，继续弹出保存的节点 */
        }
    }
}

3. 后序遍历：先左节点，然后右节点，最后根节点

a) 递归算法

void lastorder_traverse(const struct bi_tree *tree)
{
    if (tree->left) {
        lastorder_traverse(tree->left);
    }
    if (tree->right) {
        lastorder_traverse(tree->right);
    }
    access(tree->data);
}

不得不感叹递归的实现太简单了。。。

b) 非递归算法

之前的写法有错误，当从栈中弹出节点时，且该节点又有右子节点时，需要再次尝试先遍历该右子节点的所有左子节点时，会将该节点丢失。

那么，这时需要重新将该节点压栈，但是当再次弹出时，需要区分其右子节点是否已经遍历过了。所有在节点中添加了一个成员变量access。当被access函数访问时，该access被置位。

还有一个想法，看是否能够避免引入这个成员变量，暂时还没有答案。

void lastorder_traverse(const struct bi_tree *tree)
{
    struct stack s;

    init_stack(&s);

    const struct node *n = tree;

    while (n) {
        /* 沿左节点向下走 */
        while (n->left) {
            s.push(n);
            n = n->left;
        }

        do {
            /* 如果有右节点，仍然需要检查左节点 */
            if (n->right && !n->right->access) {
                /* 右节点还未访问过，需要把该节点再次压栈 */
                s.push(n);
                n = n->right;
                break;
            }

             

             /* 没有右节点，访问节点， 并弹出上一个父节点 */

            access(n->data);
        } while (n = s.pop());
    }
}

4. 按层访问：从根节点，由上及下，由左向右访问节点

a) 递归算法：

这个。。。这个。。。似乎没有递归的用武之地呵。。。

b) 非递归算法：

void layorder_traverse(const struct bi_tree *tree)
{
    /*
    这里选用queue而非stack，因为这种遍历方式需要的是FIFO，即先进先出
    */
    struct queue q;

    init_queue(&q);

    const struct node *n = tree;

    while (n) {
        /* 访问节点 */
        access(n->data);

        if (n->left) {
            /* 将左节点放入队列 */
            q.push(n);
        }

        if (n->right) {
            /* 将右节点放入队列 */
            q.push(n);
        }

         

         /* 取出下一个节点 */

        n = q.pop();
    }
}

再次说明，以上代码未经测试，只是我在纸上简单的画了画，想了一下流程。思路基本上应该没有什么问题，再次欢迎大家指正。