回 帖 发 新 帖 刷新版面

主题:精典二叉树非递归遍历的算法

遍历二叉树的非递归算法
编写的方法:根据树中结点的遍历规律及顺序直接写出其非递归算法。
先序非递归算法
【思路】
假设:T是要遍历树的根指针,若T != NULL
对于非递归算法,引入栈模拟递归工作栈,初始时栈为空。
问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针?
方法1:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,再先序遍历T的右子树。
方法2:访问T->data后,将T->rchild入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T->rchild,出栈,遍历以该指针为根的子树。
【算法1】
void    PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{    // 基于方法一,流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【算法2】
void    PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{    // 基于方法二,流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑:对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。
问题:如何用栈来保存信息,使得在中序遍历过左子树后,能利用栈顶信息获取T指针?
方法:先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。

【算法】
void    InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{    // 流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
进一步考虑:对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】

T是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法,结点入栈时,配一个标志tag一同入栈(0:遍历左子树前的现场保护,1:遍历右子树前的现场保护)。
首先将T和tag(为0)入栈,遍历左子树;返回后,修改栈顶tag为1,遍历右子树;最后访问根结点。
typedef struct stackElement{
Bitree    data;
char        tag;
}stackElemType;
【算法】
void    PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{    // 流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1);        // 设置栈顶标记
T = GetTopPointer(S);    // 取栈顶保存的指针
T = T->rchild;
}else break;
}
}

[fly]回帖[/fly][email]null[/email]

回复列表 (共13个回复)

沙发

其实不管是先序,中序,后序
都是一样的只要注意回溯时:
如果该结点是栈顶的右孩子,则继续回溯

板凳

还是实现软件的工程化比较好!!
呵呵!
其实知道一两种方法就可以拉!
中国的程序员有个特点,写的程序代码少效率高,但除了他本人谁都看不懂!!
呵呵!

3 楼

但是怎样去处理栈啊?

4 楼

hao

5 楼

只要了解到高级语言是怎样实现递归调用的,其实递归和非递归都是一样的原理,递归是算法设计思想,用于设计算法,如果你处理的问题对递归栈的要求高,系统栈不能满足的时候,就化成非递归的形式(一般能满足),软件工程的思想是算法本身是递归的就要求用递归的形式写程序,代码的可理解性更重要.

楼主的程序不错,加精了!

PS:应该是'经典',不是'精典'.

6 楼

基于同一个思想的非递归算法:
//以下的非递归算法都基于同一个思想:当当前结点是栈顶元素的右孩子,会是什么情况;    
 void PostOrder(Tree t)
{
    BitNode *stack[MAX],*p;
    int top=-1;
    p=t;
    do{
        top++;
        stack[top]=p;
        while(p->lchild!=NULL){
            p=p->lchild;
            top++;
            stack[top]=p;
        }
        while(1){
            if(p->rchild!=NULL){
                p=p->rchild;
                break;
            }
            else{
                printf("%c",p->data);
                while(1){
                    p=stack[top];
                    top--;
                    if(top==-1 ) return;
                    else if(stack[top]->rchild!=p){
                        p=stack[top];
                        break;
                    }
                    else printf("%c",stack[top]->data);
                }
            }
        }
    }while(1);
}                            

void InOrder(Tree t)
{
    BitNode *stack[MAX],*p;
    int top=-1;
    p=t;
    do{
        top++;
        stack[top]=p;
        while(p->lchild!=NULL){
            p=p->lchild;
            top++;
            stack[top]=p;
        }
        printf("%c",p->data);
        while(1){
            if(p->rchild!=NULL){
                p=p->rchild;
                break;
            }
            else{
                p=stack[top];
                top--;
                while(top!=-1&&stack[top]->rchild==p){
                    p=stack[top];
                    top--;
                }
                if(top==-1) return;
                printf("%c",stack[top]->data);
                p=stack[top];
            }
        }
    }while(1);

                                                                                      
void PreOrder1(Tree t)
{
     BitNode *stack[MAX],*p;
     int top=-1;
     p=t;
     do{
        top++;
        stack[top]=p;
        printf("%c",p->data);
        while(p->lchild!=NULL){
              p=p->lchild;
              printf("%c",p->data);
              top++;
              stack[top]=p;
        }
        while(1){
             if(p->rchild!=NULL){
                 p=p->rchild;
                 break;
             }
             else{
                  p=stack[top];
                  top--;
                  while(top!=-1&&stack[top]->rchild==p){
                        p=stack[top];
                        top--;
                  }
                  if(top==-1) return;
                  p=stack[top];
             }
        }
     }while(1);
}                                                                                       

            

7 楼


有缩进好看多了!

8 楼

常用的思想是:递归算法容易被“人”理解,在设计算法时用递归。给电脑执行时,由于为了节省系统开销,或者被系统限制(比如某些嵌入式设备的硬件架构不能支持递归)在通过递归转叠代的方法(比如引入栈)转换成循环结构。事实上这种转换的方法要比开始就设计叠代的算法要简单的多。

9 楼

用栈或者是函数递归抽象出来是否一个意思呢?

10 楼

好啊

我来回复

您尚未登录,请登录后再回复。点此登录或注册