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

相关内容

热门资讯

安卓系统写脚本软件下载,基于安... 你有没有想过,你的安卓手机或者平板电脑,除了用来刷剧、玩游戏,还能变成一个强大的工作助手呢?没错,就...
安卓系统有哪些机型好,探索顶级... 你有没有想过,安卓系统里的手机型号那么多,哪一款才是最适合你的呢?别急,今天我就来给你好好盘点看看安...
安卓系统之间如何互传,安卓设备... 你是不是也和我一样,手机里存了那么多好东西,却苦于不能和好友分享呢?别急,今天就来教你怎么用安卓系统...
安卓系统启动修改工具,安卓系统... 你有没有想过,你的安卓手机启动速度竟然可以像火箭一样快?没错,这就是今天我要跟你分享的神秘工具——安...
安卓系统版本号历史,从初生到繁... 你有没有发现,每次打开手机,那系统版本号总是一闪而过,好像在悄悄告诉你:“我可是有故事的哦!”今天,...
小米改安卓系统软件,安卓系统软... 你知道吗?最近小米手机界可是掀起了一阵小小的风波呢!那就是小米对安卓系统软件的一次大改版。这可不是什...
安卓系统控制流量app,安卓系... 你有没有发现,手机里的流量就像小河里的水,不知不觉就流光了?别急,今天就来给你揭秘一款神奇的安卓系统...
hl2240安卓系统,功能解析... 你有没有发现,最近你的手机系统更新换代的速度简直就像坐上了火箭呢?今天,就让我带你来一探究竟,看看这...
iqoo刷原生安卓系统,还原纯... 最近手机圈里可是热闹非凡呢!一款名为iqoo的新品手机,凭借其强大的性能和独特的刷机功能,吸引了无数...
安卓系统我的读书入口,我的读书... 亲爱的手机控们,你是否也有这样的体验:每天手机不离手,却总是找不到心仪的读书应用?别急,今天我要给你...
搭载安卓9系统的手机,新一代智... 你有没有发现,最近市面上新出的手机,好像都开始搭载安卓9系统了呢?这可真是让人眼前一亮啊!今天,就让...
电脑模拟安卓系统win7系统,... 你有没有想过,如果电脑也能像手机一样,随时随地都能玩各种游戏、看视频呢?想象你坐在电脑前,屏幕上突然...
华为系统如何退回安卓,轻松实现... 你有没有想过,手机系统就像是我们生活中的衣服,有时候穿久了,就想换一件新的。比如,你之前用了华为的系...
安卓系统定制防沉迷手机,安卓手... 你有没有发现,现在的手机越来越智能,但随之而来的是沉迷于手机的问题也越来越严重,尤其是对青少年来说。...
安卓系统手机顶部符号,功能解析... 你有没有注意到,每次拿起安卓系统手机,顶部那一排小小的符号总是默默守护着你的屏幕?它们就像是一群小精...
美团餐饮系统安卓版,尽享美食新... 你有没有发现,最近点外卖的时候,手机上那个美团餐饮系统安卓版真是越来越方便了!今天,就让我带你来好好...
新生活cms安卓系统进货系统,... 你知道吗?最近市面上出现了一个超级酷的新玩意儿——新生活CMS安卓系统进货系统!这可是个让商家们眼睛...
安卓系统ai文章生成,探索安卓... 你知道吗?现在手机界的风云变幻,安卓系统可是当之无愧的王者!而且,最近听说安卓系统里还悄悄加入了AI...
推荐安卓车载导航系统,安卓平台... 你有没有想过,开车的时候,如果没有导航系统,那可真是像在茫茫大海中航行,没有指南针的感觉呢?别急,今...
安卓系统的地图怎样下载,下载与... 你有没有发现,现在不管去哪里,手机地图都成了我们的好帮手?尤其是安卓系统的地图,功能强大,用起来超级...