非递归方式实现二叉树四种遍历
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,兼容性... 你有没有发现,现在手机市场上,安卓和苹果两大阵营的较量越来越激烈了?尤其是安卓手机和苹果系统APP之...
华为手机还原为安卓系统 你有没有发现,有时候华为手机用久了,系统变得有点“臃肿”,运行速度也不如以前那么流畅了呢?别急,今天...
如何把win系统程序改为安卓系... 你是不是也和我一样,手里拿着一台运行着Windows系统的电脑,却突然对安卓系统产生了浓厚的兴趣?想...
安卓系统切换电脑桌面,安卓系统... 你有没有想过,你的安卓手机和电脑桌面之间也能来个亲密接触呢?没错,就是那种无缝切换的感觉,让你在手机...
安卓系统永远在更新吗,引领智能... 你有没有发现,每次打开你的安卓手机,总感觉它像是个永不停歇的小宇宙,总是在更新更新再更新?没错,安卓...
安卓系统好用的折叠手机,安卓系... 你有没有发现,最近手机界可是热闹非凡呢!各大品牌纷纷推出了自家的折叠手机,而安卓系统的好用折叠手机更...
安卓掌机3326系统,深度解析... 你有没有听说过安卓掌机3326系统?这可是最近在游戏圈里火得一塌糊涂的存在呢!想象一台小小的掌机,却...
安卓系统的ping命令大全 你有没有想过,在安卓系统里,那些看似普通的命令其实藏着大大的秘密呢?今天,就让我带你一探究竟,揭开安...
安卓系统绘图板在哪 你有没有发现,用安卓手机画画简直是一种享受呢?不过,有时候找不着绘图板的功能,是不是让你有点头疼呢?...
安卓养老系统叫什么名,智能养老... 你有没有发现,随着智能手机的普及,我们这些“老司机”也开始对手机系统有了更高的要求?这不,最近我在网...
安卓系统刷机怎么激活 你那安卓手机是不是突然卡顿得厉害,或者想尝试一些新功能,却发现自己被困在原版系统里出不来?别急,今天...
安卓系统设置开机自启,深度解析... 你有没有发现,手机用久了,开机速度越来越慢,有时候甚至慢得像蜗牛爬?这可真是让人头疼啊!你知道吗,这...
导航大屏安卓系统版本 你有没有发现,现在汽车里的导航大屏越来越智能了?这不,最近我就在研究这些导航大屏的安卓系统版本,发现...
苹果6备份安卓系统,苹果6备份... 你有没有想过,把苹果6的备份转移到安卓系统上,这事儿听起来是不是有点儿像是在玩穿越时空的魔法?不过别...
安卓系统的彩蛋怎么进,解锁隐藏... 你有没有发现,安卓系统里藏着不少小秘密呢?今天,就让我带你一起探索安卓系统里的彩蛋,看看那些隐藏在角...
安卓系统怎么总重启,探究安卓系... 手机突然重启,是不是瞬间感觉整个人都不好了?尤其是安卓系统,有时候就像个顽皮的孩子,时不时地来个“突...
vr设备是安卓系统吗,安卓系统... 亲爱的读者,你是否曾好奇过VR设备使用的操作系统是安卓系统吗?在这个虚拟与现实交织的时代,VR设备已...
安卓2.3系统输入法 你有没有发现,手机上的输入法真的是个神奇的小玩意儿?它就像你的私人秘书,帮你把心里的话变成文字,记录...
安卓12系统来电话黑屏,安卓1... 最近是不是你也遇到了安卓12系统来电话时手机黑屏的尴尬情况?这可真是让人头疼啊!手机屏幕突然变成了一...
小米9安卓9原生系统,极致性能... 亲爱的数码爱好者们,今天我要和你聊聊一款手机,它不仅在国内市场掀起了一阵热潮,更是让全球的米粉们为之...