数据结构专题 | 先序非递归遍历二叉树
admin
2024-01-20 19:29:58
0

先序非递归遍历二叉树,主要是利用了栈的先进后出原理,用一个栈即可实现该算法,下面我们一起来看一下如何来实现吧

目录

先序建立二叉树 

先序递归遍历二叉树 

先序非递归遍历二叉树 


 

先序建立二叉树 

在进行先序非递归遍历之前,我们需要先建立一个二叉树,这里采用先序的方法建立二叉树

void Create(BiTree *t){
    BiTree q;    //树结点
    char s;       //输入的值
    scanf("%c",&s);
    getchar();
    if(s=='#'){       //当建立时某个树没有左孩子或右孩子时,我们输入一个#
        *t=NULL;   
        return;
    }
    q=(BiTree)malloc(sizeof(BiTree));    //分配内存
    q->data=s;
    *t=q;                               //根结点
    Create(&q->lchild);        //先序建立左子树
    Create(&q->rchild);        //先序建立右子树

先序递归遍历二叉树 

在建立完二叉树后,我们先来看看递归的算法是如何实现的 

void xianxu(BiTree t){
    if(!t) return;                     //当树节点为空时,返回
    printf("%c",t->data);       //打印跟结点
    xianxu(t->lchild);            //先序遍历左子树
    xianxu(t->rchild);            //先序遍历右子树

先序非递归遍历二叉树 

下面我们来看看如何非递归对二叉树进行遍历 

void fxianxu(BiTree t){
    BiTree stack[100],p;     //我们需要一个保存树结点的栈
    int top=0;     //栈顶指针
    for(int i=0;i<100;i++){
        stack[i]=0;      //初始化栈
    }
    p=t;           //根结点
    while(p){
        printf("%c",p->data);    //打印根结点
        if(p->rchild){                //先从右边开始,如果右子树不为空
            stack[top++]=p->rchild;      //右子树入栈
        }
        if(p->lchild){               //再看左子树,如果左子树非空
            p=p->lchild;           //继续遍历下一个左子树
        }else if(top>0){          //如果左子树为空但是栈不为空
            p=stack[--top];      //此时栈顶是当前树的右子树,将右子树出栈
        }else{                        //当左子树为空,且栈中没有元素时,遍历结束
            p=0;
        }
    }

以上代码理解起来有点抽象,我们举个例子来说明一下:

假设现在我们输入了AB##C##,这是棵最简单的二叉树,A是根结点,B是A的左子树,C是A的右子树,我们用非递归方法对其进行遍历,先看A的右子树,发现它有右子树,右子树是C,C入栈,再看A的左子树,发现它有左子树,左子树为B,我们令B为新的树结点,第一次循环结束,开始第二次循环,我们先看右子树,发现B没有右子树,不做任何操作,再看B的左子树,发现B也没有左子树,但是当前栈中有元素C,我们出栈,并令C为新的树结点,第二次循环结束,执行第三次循环,我们还是先看C的右子树,发现C没有右子树,不做任何操作,再看C的左子树,发现左子树为空,并且当前栈中没有元素,我们令新的树结点为空,即可跳出循环

我们最后来总结一下如何对二叉树进行先序非递归的遍历:

第一步,打印根结点

第二步,先看树结点的右子树,存在,入栈

第三步,再看树结点的左子树,存在,令其为新的树结点,不存在看该树结点右子树是否存在(就是看栈中是否有元素),存在右子树就让右子树为新的树结点继续循环,当某个树结点既没有左子树也没有右子树时结束循环 

相关内容

热门资讯

模拟安卓系统软件,软件功能与体... 你有没有想过,手机里的世界可以变得更加丰富多彩?没错,就是那种可以像安卓系统一样自由自在地玩耍的世界...
安卓换系统会卡吗,换系统会卡吗... 你有没有想过,你的安卓手机用久了,是不是也会像人一样,反应变得迟钝了呢?没错,这就是我们今天要探讨的...
平板安卓系统自动重启,安卓平板... 你是不是也遇到过这种情况?平板电脑突然间就自动重启了,是不是瞬间感觉心里一紧,心想这可怎么办呢?别急...
findx3安卓系统,安卓系统... 你有没有发现,最近手机圈里又掀起了一股热潮?没错,就是OPPO Find X3系列的安卓系统。这款系...
安卓系统删除的软件,那些曾陪伴... 手机里的软件越来越多,是不是有时候觉得内存不够用,想清理一下呢?别急,今天就来聊聊安卓系统删除软件的...
白色的手机安卓系统,安卓系统下... 你有没有发现,最近市面上那些白色的手机简直让人眼前一亮呢?尤其是搭载安卓系统的那些,简直就像是一块块...
vico是不是安卓系统,揭秘安... 最近是不是有很多小伙伴在问:“Vico手机,它是不是运行安卓系统呢?”这个问题可真是让人好奇啊!今天...
安卓10系统省电不,安卓10系... 你有没有发现,自从升级到安卓10系统,手机续航能力好像大不如前了?别急,今天就来给你揭秘安卓10系统...
cm14安卓系统,深度定制与极... 你有没有发现,你的安卓手机最近是不是有点不一样了?是不是觉得系统运行得更加流畅,界面也更加美观了呢?...
平板安卓系统咋样升级,轻松实现... 你那平板安卓系统是不是有点儿卡,想给它来个升级大变身?别急,让我来给你详细说说平板安卓系统咋样升级,...
安卓原系统在哪下载,探索纯净体... 你有没有想过,为什么安卓手机那么受欢迎?那是因为它的系统——安卓原系统,它就像是一个充满活力的魔法师...
安卓系统procreate绘图... 你有没有发现,现在手机上画画变得越来越流行了?尤其是用安卓系统的手机,搭配上那个神奇的Procrea...
电视的安卓系统吗,探索安卓电视... 你有没有想过,家里的电视是不是也在悄悄地使用安卓系统呢?没错,就是那个我们手机上常用的安卓系统。今天...
苹果手机系统操作安卓,苹果iO... 你有没有发现,身边的朋友换手机的时候,总是对苹果和安卓两大阵营争论不休?今天,咱们就来聊聊这个话题,...
安卓系统换成苹果键盘,键盘切换... 你知道吗?最近我在想,要是把安卓系统的手机换成苹果的键盘,那会是怎样的体验呢?想象那是不是就像是在安...
小米操作系统跟安卓系统,深度解... 亲爱的读者们,你是否曾在手机上看到过“小米操作系统”和“安卓系统”这两个词,然后好奇它们之间有什么区...
miui算是安卓系统吗,深度定... 亲爱的读者,你是否曾在手机上看到过“MIUI”这个词,然后好奇地问自己:“这玩意儿是安卓系统吗?”今...
安卓系统开机启动应用,打造个性... 你有没有发现,每次打开安卓手机,那些应用就像小精灵一样,迫不及待地跳出来和你打招呼?没错,这就是安卓...
小米搭载安卓11系统,畅享智能... 你知道吗?最近小米的新机子可是火得一塌糊涂,而且听说它搭载了安卓11系统,这可真是让人眼前一亮呢!想...
安卓2.35系统软件,功能升级... 你知道吗?最近在安卓系统界,有个小家伙引起了不小的关注,它就是安卓2.35系统软件。这可不是什么新玩...