登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

二叉树遍历-递归向非递归转化的通用模式  

2009-09-28 15:59:07|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/7097176720098283597120/

对于通常的尾递归很容易转换成循环。通过手工模拟我们基本上就可以确定如何进行转换。实际上尾递归的转换也可以看成是下面这种模式的特殊情况,在这种模式下,尾递归只是一个这样的递归树。

二叉树遍历-递归向非递归转化的通用模式 - 星星 - 银河里的星星

递归向非递归的转化,最简单的方法就是利用栈。但是对于比较复杂的递归转换起来即使利用栈也比较困难,所以试图寻找一种容易理解的递归向非递归转换的一般模式,通过这种模式可以很容易的写出非递归形式。以前的算法书籍,比如<<算法引论>>对这个问题有专门的介绍。因为一方面栈的空间是比较小的,这样递归有可能导致栈溢出;另一方面有些老的程序语言,并不支持递归。这样就有非递归化的需求。但是之前看到的一些非递归化的方法有些形式化,也不容易记忆和理解。所以这里试图建立一种更近直白容易理解的非递归化方法。

实际上在<<算法导论>>里,关于递归复杂度的分析方法中,有一个是通过递归调用树来进行计算的。也就是说递归调用的整个过程是可以用一棵树表示出来的,这样一课树画出来之后,只要再确定一个遍历顺序就可以了。可以看到,递归的顺序实际上就是dfs的遍历顺序,所以我们只要可以用迭代实现dfs,然后将它应用到递归调用树上,就可以将递归程序用迭代表达出来了。

二叉树的各种遍历是我们最经常见到的递归程序,当然很多题目也是要求实现后序,中序或者前序的非递归遍历。可以看到,递归程序就是在这样的一棵树中遍历,当然散落在递归调用间的处理程序,实际上也可以标在递归树的边上,也就是说,只要我们把递归画成一棵树,然后把递归程序里面的除了递归调用之外的代码加到相应的路径处,然后在用dfs遍历时,在经过相应的边时,加上相应的处理程序就可以了。这样就把递归程序,与递归树建立其了对应关系。

其中包含了两个步骤:

一.画出递归树

二.将额外的处理代码加入递归树中相对应的位置,从下图中可以看到递归程序中的1 2 3 4以及与递归树中对应的1 2 3 4的位置。(我们只画出来了根节点的对应部分,实际上所有节点都具有根节点的形式)

看下面的程序和二叉树

void preorder(node * root){   

    //1 
    if(root == NULL) return;
    printf("%d ",root -> key);
    preorder(root -> left);

    //2
   
    //3

    preorder(root -> right);

    //4 

}

二叉树遍历-递归向非递归转化的通用模式 - 星星 - 银河里的星星

下面再来看dfs的非递归程序是如何实现的,实际上使用了一个隐式栈。这里我们定义三种节点:活结点,死结点,待扩展节点。

从图中来看,绿色的代表活结点,红色的代表死结点,剩下的代表未访问节点,待扩展节点则代表当前处理的节点即栈顶节点。在整个处理过程中,栈中保存的是所有的活结点,而活结点实际上就是当前位置到根节点的路径上的所有节点。如果当前节点还有扩展节点,就把它压入栈,然后再以当前节点为扩展节点,否则该节点就是死结点,将它pop出栈即可。dfs的迭代的一般模式如下:(引自王晓东 <<算法设计与分析>> 第5章回溯法)


void iterative_Backtrack(){
int t = 1;

while(t > 0){//如果栈未空

   //则扩展当前栈顶节点

   if(f(t) <= g(t)) //f[t],g[t]可以看成是栈里第t个元素代表的那个节点未搜索过的起始节点和终止节点编号

   for(int i = f(t) ; i <= g(t) ; i++){ //->>>>实际上应该改为while(f(t) <= g(t))

        x[t] = h(i);//将栈顶元素设为h[i],当然还有些需要做的工作没有写出来,需要修改f(t)和h(t)的内容

        if(constraint(t) && bound(t)){//如果可行
        if(solution(t)) output(t);//如果是解则直接输出  

        else  t++; //否则继续扩展,
        }

       //虽然是个for循环,但是实际上当前节点只扩展了一个节点,之后该扩展节点又变成了当前扩展节点,

       //t++正是带来了这样的影响,在下一个for循环中,当然实际上这段代码还有些问题。
   }//end of for

   else  t--;//如果不存在扩展节点,则将当前元素出栈,称为死结点 
}//end of while

}//end of func

分析上面的程序,实际上模式很简单:

初始我们可以把根节点压栈。

之后开始迭代。迭代中,我们把栈顶节点作为待扩展节点,然后我们看栈顶节点应该扩展那个节点了,这里需要一个数组来记录栈中节点已经扩展到哪个节点了,也就是里面的f数组。如果栈顶节点还有可扩展节点,那么我们就把这个可扩展节点放到栈里(很明显这个过程中需要更新f[t]的值),然后进行下一次的迭代。如果栈顶节点已经没有可扩展的节点了,说明以该节点为根的子树已经处理完毕,这样该节点就应该出栈,变成死结点了,然后开始下一次的迭代。如果栈中还有节点,就说明需要继续进行迭代,否则就终止。


下面我们将它应用到二叉树遍历中:
实际上下面的程序里,并没有建立用来保存栈中第t个元素的起始和终止扩展节点的f[],g[]数组,因为对于儿叉树来说,每个节点最多只有两个扩展节点,所以这里是通过直接判断确定当前节点该如何扩展的,也就是说下面程序的那些条件判断就代替了上面的dfs迭代中的那个for循环。

下面是后序遍历的非递归版本,可以看到我们在这里把printf操作,加到了所有的pop操作之后,这也正是后序访问的时机。
/*postorder*/
void non_recursive_stack_postorder(struct node * root){
    struct node * temp,*last;
    push(root);
    while(!isempty()) {
       //查看当前栈顶节点,也就是待扩展节点
        temp = stack[top];

        //如果左右孩子皆为空
        if((temp->left == NULL && temp -> right == NULL)){               
            last = pop();
            printf("%d ",last -> key);
            ///printf("%d ",temp -> key);
            continue;   
        }
        //如果是从左子树回溯来的,则应该扩展右孩子了
        if(last == temp -> left){
            ///printf("%d ",temp -> key);
            //如果右子树不为空   
            if(temp -> right != NULL){push(temp->right);continue;}
            //如果右子树为空
            else {last = pop() ; printf("%d ",last -> key);continue ; }   
        }
        //如果是右子树回溯过来的,说明当前节点已经没有可扩展节点了,应该出栈变成死结点
        if(last == temp -> right ){
            last = pop();
            printf("%d ",last -> key);
            continue;   
        }
        //如果栈顶节点不是回溯到达的,而是刚加入的节点,则应该从左子树开始扩展
        if(temp -> left != NULL){
           push(temp -> left);
           //printf("%d ",temp -> left -> key);
           continue;    
        }
 //如果栈顶节点不是回溯到达的,而是刚加入的节点,但是左子树为空
        if(temp -> right != NULL){
           ///printf("%d ",temp -> key);
           push(temp -> right);    
           //printf("%d ",temp -> right -> key);
           continue;    
        }

    }

}


如果要改成前序,也很简单,只要把所有的print操作写到push操作前面即可。也就是图中的红色两句printf。
如果要修改成中序,观察程序可以看到,有三个可能的时机,一种是左子树为空,另一种是左右子树皆为空,最后一种是从左子树回溯过来的时候。也就是上面代码中对应的绿色三句,它们打印的就是中序遍历的结果。

从上面这个程序可以看成,我们只要正确的安排打印的顺序,就可以正确的实现前中后序的非递归遍历了。实际上我们观察前中后序的递归版本也可以看出,它们遍历的递归调用结构其实是一样的,不同的就在于节点打印的时机。

另外实际上也可以不采用上面的这种用栈+dfs的迭代实现的方法,比如前序可以简单的这样实现:

void non_recursive_stack_preorder(struct node * root){
    struct node * temp;
    push(root);
    while(!isempty()){
        temp = pop();
        printf("%d ",temp -> key);
        if(temp -> right != NULL)
            push(temp -> right);
        if(temp -> left != NULL)
            push(temp -> left);

    }
}

ps:
有的题目也有这样的要求,就是不让使用栈来实现二叉树的非递归遍历。实际上这样的题目通常是因为,树节点还有一个特殊的变量:指向父节点的指针。利用这个指针实际上就可以实现类似于栈的功能了。再结合我们的程序中的方法:就是比较上一个pop出来的节点与当前节点的左右孩子是否相等,我们就可以确定当前节点处在什么样的扩展状态。


 

  评论这张
 
阅读(2460)| 评论(1)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018