非递归方式实现二叉树四种遍历
admin
2024-01-20 21:18:42
0

问题描述 

【问题描述】

非递归方式实现二叉树的先序遍历、中序遍历、后序遍历和层序遍历。

提示:(1)利用先序建立二叉树序列;(2)求四种遍历结果。

【输入形式】

(1)先序建立二叉树序列

(2)非递归方式遍历

【输出形式】

四种遍历结果

【样例输入】

ABD#G###CE##FH###

【样例输出】

PreOrder:ABDGCEFH

InOrder:DGBAECHF

PostOrder:GDBEHFCA

CcOrder:ABCDEFGH

【评分标准】:四种遍历必须以非递归方式实现。

程序实现 

#include
#include
#define MAX 20

typedef struct BitNode
{
    char data;
    struct BitNode *lchild,*rchild;
}BitNode,*BiTree;

typedef struct SqQueue
{
    int data[MAX];
    int rear,front;
}SqQueue;

void Creat (BiTree *t)
{
    char s;
    BiTree p;
    scanf("%c",&s);
    if(s=='#')
    {
        *t=0;
        return;
    }
    p=(BiTree)malloc(sizeof(BitNode));
    p->data=s;
    *t=p;
    Creat(&p->lchild);
    Creat(&p->rchild);
}

void Pre_n(BiTree p)
{
    BiTree stack[MAX],q;
    int top=0,i;
    for(i=0;i     stack[i]=0;
    q=p;
    while(q)
    {
        printf("%c",q->data);
        if(q->rchild)
            stack[top++]=q->rchild;
        if(q->lchild)
            q=q->lchild;
        else if(top>0)
                q=stack[--top];
             else
                 q=0;
    }
}

void In_n(BiTree t)
{
    BiTree stack[MAX],p;
    int top=0;
    p=t;
   if(p)
   {
       while(p||top>0)
       {
           while(p)
           {
               stack[top++]=p;
               p=p->lchild;
           }
           if(top>0)
           {
               p=stack[--top];
               printf("%c",p->data);
               p=p->rchild;
           }
       }
   }
}

void Post_n(BiTree t)
{
    BiTree stack[MAX],p;
    int i,top=0,flag[MAX];
    for(i=0;i     {
        stack[i]=0;
        flag[i]=0;
    }
    if(!t)
        return;
    p=t;
    while(p||top>0)
    {
        if(p)
        {
            stack[top]=p;
            flag[top++]=1;
            p=p->lchild;
        }
        else
        {
            p=stack[top-1];
            if(flag[top-1]==1)
            {
                flag[top-1]=2;
                p=p->rchild;
            }
            else
            {
                printf("%c",p->data);
                top--;
                p=0;
            }
        }
    }
}

void CcOrder (BiTree t)
{
    BiTree p;
    SqQueue qlist,*q;
    q=&qlist;
    q->rear=0;
    q->front=0;
    p=t;
    if(p)
    {
        printf("%c",p->data);
        q->data[q->rear]=p;
        q->rear=(q->rear+1)%MAX;
        while(q->front!=q->rear)
        {
            p=q->data[q->front];
            q->front=(q->front+1)%MAX;
            if(p->lchild)
            {
                printf("%c",p->lchild->data);
                q->data[q->rear]=p->lchild;
                q->rear=(q->rear+1)%MAX;
            }
            if(p->rchild)
                {
                    printf("%c",p->rchild->data);
                    q->data[q->rear]=p->rchild;
                    q->rear=(q->rear+1)%MAX;
                }
        }
    }
}
int main()
{
    BiTree t=0;
    Creat(&t);
    if(!t)
        printf("");
    else
    {
        printf("PreOrder:");
        Pre_n(t);
        printf("\n");
        printf("InOrder:");
        In_n(t);
        printf("\n");
        printf("PostOrder:");
        Post_n(t);
        printf("\n");
        printf("CcOrder:");
        CcOrder(t);
        printf("\n");
        return 0;
    }

相关内容

热门资讯

安卓系统用的华为应用,探索智能... 你知道吗?在安卓系统里,华为的应用可是个宝库呢!它们不仅功能强大,而且使用起来超级方便。今天,就让我...
安卓变ios系统魅蓝 你知道吗?最近有个朋友突然告诉我,他要把自己的安卓手机换成iOS系统,而且还是魅蓝品牌的!这可真是让...
幻书启世录安卓系统,安卓世界中... 亲爱的读者们,你是否曾在某个夜晚,被一本神奇的书所吸引,仿佛它拥有着穿越时空的力量?今天,我要带你走...
电脑安装安卓系统进不去,安卓系... 电脑安装安卓系统后竟然进不去,这可真是让人头疼的问题啊!你是不是也遇到了这种情况,心里直呼“怎么办怎...
用键盘切换控制安卓系统,畅享安... 你有没有想过,用键盘来控制你的安卓手机?是的,你没听错,就是那个我们每天敲敲打打的小玩意儿——键盘。...
小米安卓镜像系统在哪,小米安卓... 你有没有想过,你的小米手机里有一个隐藏的宝藏——安卓镜像系统?没错,就是那个可以让你的手机瞬间变身成...
安卓手机下载排班系统,高效排班... 你有没有想过,每天忙碌的工作中,有没有什么好帮手能帮你轻松管理时间呢?今天,就让我来给你介绍一个超级...
桌面组件如何弄安卓系统,桌面组... 亲爱的桌面爱好者们,你是否曾梦想过将安卓系统搬到你的电脑桌面上?想象那些流畅的动画、丰富的应用,还有...
安卓13系统介绍视频,新功能与... 亲爱的读者们,你是否对安卓13系统充满好奇?想要一探究竟,却又苦于没有足够的时间去研究?别担心,今天...
车机安卓7.1系统,功能升级与... 你有没有发现,现在的车机系统越来越智能了?尤其是那些搭载了安卓7.1系统的车机,简直就像是个贴心的智...
安卓系统下如何读pdf,And... 你有没有遇到过这种情况:手机里存了一大堆PDF文件,可是怎么也找不到一个能顺畅阅读的工具?别急,今天...
安卓系统全国通用的吗,畅享智能... 你有没有想过,为什么你的手机里装的是安卓系统呢?安卓系统,这个名字听起来是不是有点神秘?今天,就让我...
假苹果手机8安卓系统,颠覆传统... 你有没有想过,如果苹果手机突然变成了安卓系统,会是怎样的景象呢?想象那熟悉的苹果外观,却运行着安卓的...
安卓12.0系统vivo有吗,... 你有没有听说最近安卓系统又升级啦?没错,就是那个让手机焕然一新的安卓12.0系统!那么,咱们国内的手...
核心芯片和安卓系统,探索核心芯... 你知道吗?在科技的世界里,有一对“黄金搭档”正悄悄改变着我们的生活。他们就是——核心芯片和安卓系统。...
如何调安卓系统屏幕颜色,安卓系... 亲爱的手机控们,你是否曾觉得安卓系统的屏幕颜色不够个性,或者是因为长时间盯着屏幕而感到眼睛疲劳?别担...
旧台式电脑安装安卓系统,轻松安... 你那台旧台式电脑是不是已经服役多年,性能逐渐力不从心,却又不忍心让它退役呢?别急,今天就来教你怎么给...
美国要求关闭安卓系统,科技霸权... 美国要求关闭安卓系统:一场技术革新还是政治博弈?在数字化时代,智能手机已经成为我们生活中不可或缺的一...
安卓系统日记本 你有没有发现,手机里的安卓系统日记本,简直就是记录生活点滴的宝藏库呢?想象每天忙碌的生活中,有没有那...
安卓手机广告最少的系统,探索安... 你有没有发现,用安卓手机的时候,广告总是无处不在,让人烦得要命?不过别急,今天我要给你揭秘一个秘密—...