数据结构专题 | 先序非递归遍历二叉树
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的左子树,发现左子树为空,并且当前栈中没有元素,我们令新的树结点为空,即可跳出循环

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

第一步,打印根结点

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

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

相关内容

热门资讯

安卓 加密文件系统,安全存储与... 你知道吗?在安卓的世界里,有一个神秘的守护者,它就是安卓加密文件系统。今天,就让我带你一探究竟,揭开...
斑马系统怎么刷安卓,轻松实现系... 亲爱的读者,你是否曾想过给你的安卓设备来一次焕然一新的变身?没错,就是那种让你的手机瞬间变得与众不同...
怎样让安卓系统更新系统,轻松实... 亲爱的安卓用户们,你是否也和我一样,时不时地收到系统更新的提示,却总是犹豫不决,担心更新后手机会变慢...
如何看自己安卓系统,自我诊断与... 你有没有想过,你的安卓手机里那个默默无闻的系统,其实是个超级英雄呢?它每天都在为你保驾护航,从早晨闹...
安卓系统怎么拼写啊,Andro... 你问这个问题可真是戳中了我的技术盲区呢!安卓系统,这个名字听起来是不是很熟悉,就像你的手机里那个无所...
华为安卓系统被停用,挑战与转型... 你知道吗?最近科技圈可是炸开了锅!华为安卓系统被停用,这可不是一个小新闻哦。咱们得好好聊聊这个话题,...
安卓王者荣耀观战系统,沉浸式观... 亲爱的手机游戏爱好者们,你是否曾在王者荣耀的战场上,因为错过队友的精彩操作而扼腕叹息?或者,你是否渴...
怎么加安卓12系统,安卓12系... 你有没有发现,安卓系统每次更新都像是在给我们的小手机来一次华丽变身呢?这不,安卓12已经悄悄地来了,...
安卓系统阿联酋航空积分,便捷积... 你有没有想过,你的安卓手机里那些累积的积分,竟然可以在阿联酋航空的旅途中派上大用场?没错,就是那个带...
安卓系统录音文件位置,录音文件... 你有没有遇到过这种情况:手机里突然冒出了很多录音文件,但你就是找不到它们藏在哪里?别急,今天就来给你...
安卓灵动岛系统自带,智能交互新... 你知道吗?最近安卓手机界可是掀起了一股不小的风潮,那就是——安卓灵动岛系统自带功能!是不是听起来就让...
安卓支持ios系统下载,下载体... 你知道吗?最近在科技圈里可是掀起了一股小小的热潮呢!那就是安卓手机竟然支持iOS系统下载应用了!是不...
火山安卓加验证系统,安全与便捷... 你知道吗?在科技飞速发展的今天,手机安全可是个大问题。尤其是安卓系统,作为全球使用最广泛的操作系统之...
简化系统app安卓版,高效便捷... 你有没有发现,现在的生活节奏越来越快,信息爆炸的时代,我们每天都要处理海量的数据和信息。在这个时候,...
surfacepro2安卓系统... 你有没有想过,一台笔记本电脑竟然能像智能手机一样灵活多变?没错,今天我要跟你聊聊的就是这款神奇的设备...
安卓手机车联网系统,智能驾驶的... 你有没有发现,现在开车出门,手机已经成了我们离不开的好伙伴?没错,说的就是那个神奇的安卓手机车联网系...
将安卓系统数据导入ios系统,... 你是不是也有过这样的经历:手机里存满了珍贵的照片、联系人、应用数据,突然有一天,你决定换一台iPho...
雷霆战机 安卓最低系统,系统要... 你有没有听说过这款超级酷炫的飞行游戏——雷霆战机?没错,就是那个让你一上手就停不下来的刺激游戏!今天...
电脑独立安装安卓系统,探索电脑... 电脑独立安装安卓系统:探索未来的可能性在当今这个数字化时代,电脑已经不仅仅是一个用来打字的工具,它更...
树莓派虚拟安卓系统,打造便携式... 你有没有想过,用树莓派来运行安卓系统?听起来是不是有点酷炫?想象一个迷你的小树莓派,竟然能变身成为一...