对二叉树递归和非递归方式的遍历代码实现

对二叉树递归和非递归方式的遍历代码实现,第1张

首先先来看递归的三种方式,比较简单 中序递归方式遍历二叉树

void  InOrder( BiTree T ){

        if(T !=NULL){

                InOrder(T->lchild);   //对左子树进行递归遍历

                visit(T);   //这里visit函数可以自己单独写,这里相当于对节点进行访问

                InOrder(T->rchilder);  //对右子树进行递归遍历

                }

}

后序递归方式遍历二叉树
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);  //递归后序遍历左子树
        PostOrder(T->rchild);  //递归后序遍历右子树
        visit(T);  //访问根节点
        }
}
前序递归遍历二叉树
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);  //访问根节点
        PretOrder(T->lchild);  //递归先序遍历左子树
        PretOrder(T->rchild);  //递归先序遍历右子树
        }
}
接下来看非递归的三种方式遍历二叉树的代码实现

                                   

中序非递归方式实现遍历算法
void InOrder2(BiTree T){
    InitStack(S);  //初始化一个栈用来暂存需要用到的结点
    BiTree p = T;  //建一个p指针指向T的根节点,表示当前正在 *** 作的结点
    while(p || !IsEmpty(S) )//如果p是非空或者栈里面是非空那么执行以下代码
    {


        if(p) {push(T,p); p=p->lchild;}//中序是出栈的时候才访问,至于该不该访问入栈的p,要先
                                          判断p的左面是否访问完,先不管p,让它入栈,
                                          然后p继续指向左孩子。


        else{Pop(S,p);//把栈顶指针出栈,因为它左面是空的了,该访问它了
        visit(p);
        p=p->rchild;
        }



    }



}

 

后序非递归遍历二叉树算法
void PostOrder2(BiTree T){
    InitStack(S);  //初始化一个栈用来暂存需要用到的结点
    BiTree p = T;  //建一个p指针指向T的根节点,表示当前正在 *** 作的结点
    while(p || !IsEmpty(S) )//如果p是非空或者栈里面是非空那么执行以下代码
    {


        if(p) {push(T,p); p=p->lchild;}//后序也是出栈的时候才访问,至于该不该访问入栈的p,
                                            要先判断p的左面和右面是否访问完,先不管p,
                                            让它入栈,然后p继续指向左孩子。


        else{GetTop(S,p);//左面是空的了,但是不能出栈刚入栈的元素,因为还要判断右面是不是空的

             if(p->rchild && p->rchild!=r){p=p->rchild;}
             else{Pop(S,p);//说明右面是空的或者已经被访问过了,将栈顶元素出栈即可
                  visit(p);
                  p=NULL;
                 }

             p=p->rchild;
            }



    }



}
前序非递归遍历二叉树算法
void PreOrder2(BiTree T){
    InitStack(S);  //初始化一个栈用来暂存需要用到的结点
    BiTree p = T;  //建一个p指针指向T的根节点,表示当前正在 *** 作的结点
    while(p || !IsEmpty(S) )//如果p是非空或者栈里面是非空那么执行以下代码
    {


        if(p) { visit(p);
                push(T,p); p=p->lchild;
               }//前序是先访问然后入栈,只要它左面判断是空的了,就将它
                                          出栈


        else{    Pop(S,p);//把栈顶指针出栈,因为它左面是空的了,该让p指向右面的结点了
                p=p->rchild;//如果右面是空的说明下次循环p是NULL,还要继续把栈顶元素出栈
             }


    }



}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/2991007.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表(0条)

保存