所有递归算法都可以转化成非递归算法吗?

是的。一般的转换思路,无非是利用栈模拟操作系统的工作过程。不过这类的通用方法太过复杂,本文仅以最典型的二叉树的递归遍历算法转非递归遍历算法为例。

二叉树的前序、中序、后序的递归遍历算法:

void PreOrder(Tree t)
{
    if(!t) return;
    visit(t);
    PreOrder(t->lChild);
    PreOrder(t->rChild);
}
void InOrder(Tree t)
{
    if(!t) return;
    PreOrder(t->lChild);
    visit(t);
    PreOrder(t->rChild);
}
void PreOrder(Tree t)
{
    if(!t) return;
    PreOrder(t->lChild);
    PreOrder(t->rChild);
    visit(t);
}

递归算法中,有一类只在递归函数的尾部调用递归,称之为尾递归,尾递归非常容易转换为非递归算法。这是因为尾递归中的非递归语句visit()的执行次序与函数的调用次序相同,每当有一个函数执行时,将它入栈,当他出栈后就可以执行它所对应的非递归语句visit()。

二叉树的前序遍历正是尾递归:

void PreOrder(Tree t)
{
    if(t) stack.push(t);  //根节点入栈
    while(!stack.empty()){
        t = stack.pop();
        visit(t->data);   //非递归语句在出栈后执行
        if(t->rChild) stack.push(t->rChild);  //右孩子先入后出
        if(t->lChild) stack.push(t->lChild);
    }
}

非尾递归显然不能这么做,因为在非尾递归中,visit()的执行次序与函数的调用次序没啥关系,甚至有可能函数先调用visit()最后才被执行到。

中序遍历显然不是尾递归,我们需要换一种思路。首先一直往左子树走,沿途节点入栈,当前到再没有左子树的节点时,访问它,再访问它右子树,当右子树访问完成后,相当与上一层的左子树访问完了…代码如下:

void in_traversal(struct tree t,void visit(struct tree_node *e))
{
    struct tree_stack s = tree_init_stack();
    struct tree_node *x = t.top->left_child;

    while (1) {
        // 一直往左子树走,沿途节点入栈
        while (x != NULL) {
            tree_push(s,x);
            x = x->left_child;
        }

        // 若栈空退出循环
        if (s.size==0) break;

        // 当前节点没有左子树时,访问它,再访问它右子树
        x = tree_pop(&s);
        visit(x);
        x = x->right_child;
    }
}

其实先序遍历也完全可以用这种思路来实现,只不过visit()的执行次序放到入栈前:

void pre_traversal(struct tree t,void visit(struct tree_node *e))
{
    struct tree_stack s = tree_init_stack();
    struct tree_node *x = t.top->left_child;

    while (1) {
        // 一直往左子树走,沿途节点入栈
        while (x != NULL) {
            visit(x);
            tree_push(s,x);
            x = x->left_child;
        }

        // 若栈空退出循环
        if (s.size==0) break;

        // 当前节点没有左子树时,访问它,再访问它右子树
        x = tree_pop(&s);
        x = x->right_child;
    }
}

后序遍历

void postOrder(Tree T)
{
    InitStack(S);
    p=T;
    r = Null;
    while(p || ! isEmpty(S)){
        if(p){
            push(S,p);
            p=p->lchild;
        }else{
            GetTop(S,p);
            if(p->rchild && p->rchild!=r){
                p=p->rchild;
                push(S,p);
                p=p->lchild;
            }else{
                pop(S,p);
                visit(p->data);
                r=p;
                p=Null;
            }
        }
    }
}
posted @ 2020-07-17 17:40:20
评论加载中...

发表评论