非递归方式实现二叉树四种遍历
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;
    }

相关内容

热门资讯

安卓4.4系统tv软件,探索安... 亲爱的读者们,你是否曾为家里的电视屏幕增添一些智能的魔力而烦恼?别担心,今天我要给你带来一个超级实用...
安卓系统的研究人物,安卓系统发... 你知道吗?在科技飞速发展的今天,安卓系统可是占据了智能手机市场的大半壁江山。而在这片广阔的天地里,有...
山寨苹果刷会安卓系统,安卓系统... 你知道吗?在科技圈里,总有一些让人眼前一亮的小秘密。今天,我要给你揭秘一个关于山寨苹果刷安卓系统的神...
安卓系统新用户登录,畅享智能生... 你刚刚入手了一台全新的安卓手机,是不是有点小激动呢?别急,别急,让我来给你详细介绍一下安卓系统新用户...
安卓8.0系统推荐版本,体验流... 你有没有发现,手机系统更新换代的速度简直就像小孩子的成长一样快?这不,安卓8.0系统已经悄悄地来到了...
安卓系统怎么分享位置吗,一键操... 你是不是也有过这样的经历:和朋友约好见面,却因为找不到对方而急得团团转?别担心,今天就来教你怎么在安...
安卓系统更新加速器,畅享极速升... 你有没有发现,手机更新系统的时候总是慢吞吞的,让人等得心痒痒?别急,今天就来给你安利一款神器——安卓...
百答系统和安卓系统区别,差异解... 你有没有想过,为什么你的手机里装了那么多应用,却还是觉得信息不够全面?其实,这背后的大脑——操作系统...
安卓锁系统设置软件,软件设置与... 手机里的秘密可多了去了,是不是有时候你也会觉得,这手机里的信息要是被别人看到了可怎么办呢?别担心,今...
安卓电视u盘游戏系统,轻松畅享... 你有没有想过,家里的安卓电视也能玩上那些刺激的电脑游戏呢?没错,就是那种让你一玩就停不下来的游戏!今...
挂载安卓系统为读写权限,读写权... 你有没有想过,你的手机里那些神奇的安卓系统,竟然可以赋予某些应用读写权限?这听起来是不是有点像科幻电...
安卓12系统怎么打补丁,保障设... 亲爱的安卓用户们,你是否也遇到了系统卡顿、bug频发的小烦恼呢?别急,今天就来给你支个招——安卓12...
客厅电脑用安卓系统好吗,体验智... 亲爱的读者,你是不是在为客厅电脑选择操作系统而烦恼呢?安卓系统,这个我们日常手机上常见的操作系统,是...
安卓系统能看访客记录,轻松查看... 你有没有想过,你的安卓手机里藏着一个小秘密?没错,就是访客记录!是的,你没听错,你的手机里竟然能查看...
印度安卓系统电脑推荐,性能卓越... 你有没有想过,在印度这片神奇的土地上,用一台安卓系统电脑会是怎样的体验呢?想象阳光洒在泰姬陵的白色大...
安卓系统合作公司,安卓系统合作... 你知道吗?在科技的世界里,安卓系统可是个超级明星呢!它不仅拥有庞大的用户群体,还吸引了一大批合作公司...
苹果表有安卓系统时间,时间同步... 你有没有发现,最近苹果表也开始支持安卓系统了?没错,就是那个一直以封闭著称的苹果,竟然也开始拥抱安卓...
原生安卓系统裁剪图片,原生安卓... 你有没有发现,用原生安卓系统拍照,有时候拍出来的照片分辨率超高,但就是有点大,想裁剪却不知道怎么操作...
安卓系统蓝牙开关APP,安卓系... 你有没有遇到过这种情况:手机里的安卓系统蓝牙开关总是让人摸不着头脑?有时候想开蓝牙,却找不到开关在哪...
安卓系统能登录ios系统王者吗... 你有没有想过,安卓系的手机能不能登录iOS系统的王者荣耀呢?这可是个让人好奇不已的问题哦!毕竟,两个...