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

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

第一步,打印根结点

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

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

相关内容

热门资讯

安卓系统的地图怎样下载,下载与... 你有没有发现,现在不管去哪里,手机地图都成了我们的好帮手?尤其是安卓系统的地图,功能强大,用起来超级...
安卓9.0系统挂机游戏,轻松享... 你有没有发现,自从安卓9.0系统更新后,手机里的游戏体验简直就像坐上了火箭!今天,就让我带你一起探索...
安卓系统怎么用迅雷下载,安卓系... 你有没有想过,在安卓系统上下载文件竟然也能这么简单?没错,今天就要来给你揭秘,如何用迅雷在安卓系统上...
安卓手机刷成学生系统,探索全新... 你有没有想过,你的安卓手机其实可以变身成一个充满学习氛围的学生系统呢?没错,就是那种看起来简洁、功能...
ios能迁移安卓系统吗,iOS... 你有没有想过,你的iPhone里的那些宝贝应用,能不能搬到安卓手机上继续使用呢?这可是不少手机用户的...
荣耀10安卓11系统,畅享极致... 你知道吗?最近手机界可是热闹非凡呢!荣耀10这款手机,自从升级到了安卓11系统,简直就像脱胎换骨了一...
安卓系统pc版电脑配置,打造流... 你有没有想过,安卓系统竟然也能在电脑上运行呢?没错,就是那个我们手机上常用的安卓系统,现在也能在PC...
tcllinux系统刷安卓系统... 你有没有想过,你的TCL Linux系统竟然也能升级成安卓系统呢?没错,就是那个我们日常使用的安卓系...
安卓13系统更新蓝牙,蓝牙功能... 你有没有发现,最近你的安卓手机好像变得不一样了?没错,就是那个神秘的安卓13系统更新,它悄悄地来到了...
安卓系统钉钉打开声音,安卓系统... 你有没有遇到过这种情况?手机里装了钉钉,可每次打开它,那声音就“嗖”地一下跳出来,吓你一跳。别急,今...
理想汽车操作系统安卓,基于安卓... 你有没有想过,一辆汽车,除了能带你去你想去的地方,还能像智能手机一样,给你带来智能化的体验呢?没错,...
安卓系统越狱还能升级吗,升级之... 你有没有想过,你的安卓手机越狱后,还能不能愉快地升级系统呢?这可是不少手机爱好者关心的大问题。今天,...
安卓系统蓝牙耳机拼多多,畅享无... 你有没有发现,最近蓝牙耳机在市场上可是火得一塌糊涂呢!尤其是安卓系统的用户,对于蓝牙耳机的要求那可是...
安卓变苹果系统桌面,桌面系统变... 你知道吗?最近有个大新闻在科技圈里炸开了锅,那就是安卓用户纷纷转向苹果系统桌面。这可不是闹着玩的,这...
鸿蒙系统怎么下安卓,鸿蒙系统下... 你有没有想过,你的手机里那个神秘的鸿蒙系统,竟然也能和安卓世界来一场亲密接触呢?没错,今天就要来揭秘...
手机安卓系统流程排行,便捷操作... 你有没有发现,现在手机的世界里,安卓系统就像是个大舞台,各种版本层出不穷,让人眼花缭乱。今天,就让我...
安卓系统左上角hd,左上角HD... 你有没有发现,每次打开安卓手机,左上角那个小小的HD标识总是默默地在那里,仿佛在诉说着什么?今天,就...
安卓系统软件文件,架构解析与功... 你有没有发现,手机里的安卓系统软件文件就像是一个神秘的宝库,里面藏着无数的宝藏?今天,就让我带你一起...
安卓系统输入法回车,探索安卓输... 你有没有发现,在使用安卓手机的时候,输入法回车键的奇妙之处?它就像是我们指尖的魔法师,轻轻一点,文字...
安卓修改系统时间的软件,轻松掌... 你有没有想过,有时候手机上的时间不对劲,是不是觉得生活节奏都被打乱了?别急,今天就来给你揭秘那些神奇...