秃头“种树”，“种树”秃头 2021-01-28

秃头种树，种树秃头

- 7:15~7:20 打卡学习
- 8：00~10：00 复习物理
- 18：40~23：40 学习队列、三种基本遍历方法和层次遍历

7:15~7:20 打卡学习

8：00~10：00 复习物理

18：40~23：40 学习队列、三种基本遍历方法和层次遍历

哎呀呀，虽然说昨天我弄懂了先序遍历，但是对比博客上各路大佬的代码我发现我昨天的代码其实并不完善，因为其他代码里都用到了队列的知识。

所以我今天花了很长时间学习队列和栈的建立，也找了很多博客上的文章来看，但是因为用C语言写二叉树层次遍历的很少，所以我看了这么久才堪堪到似懂非懂的地步。

哎，在我百思不得其解的时候，亲爱的派大星小盆宇就着他的C++代码给我讲了一遍，于是我有了信心开始尝试敲层次遍历，竟然一遍过题了嘿嘿。

第一题如下：

问题 D: 二叉树的建立

描述

给定一个序列，按先序序列建立二叉树。输出建立后的二叉树的从上到下层次遍历序列。

格式

输入格式

一个序列

输出格式

从上之下层次序列

样例

样例输入 Copy

ABC##DE#G##F###

样例输出 Copy

ABCDEFG

*一开始我怎么也想不明白我用先序建立的树怎么才可以做到层次输出（其实这个时候我是看懂了层次遍历的），后来我想明白了——*无论我是用哪种遍历方式建的树，树都是一样的，直接敲代码输出就好

代码如下：

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct TREE)

struct TREE
{
    char data;
    struct TREE*l,*r;
};
typedef struct TREE A;
struct QUEUE
{
    A queue[100];
    int head,tail;
} Q;
typedef struct QUEUE B;
A* fun1()//先序建立二叉树
{
    A* p;
    p=(A*)malloc(LEN);
    char x;
    scanf("%c",&x);
    if(x=='#')
        p=NULL;
    else
    {
        p->data=x;
        p->l=fun1();
        p->r=fun1();
    }
    return p;
}
int fun2(A *p)//层次输出树
{
    A temp;
    if(p==NULL) return 0;
    printf("%c",p->data);
    Q.head=0,Q.tail=0;
    Q.queue[Q.tail++]=*p;
    while(Q.head!=Q.tail)
    {
        temp=Q.queue[Q.head++];
        if(temp.l!=NULL)
        {
            printf("%c",temp.l->data);
            Q.queue[Q.tail++]=*temp.l;
        }
        if(temp.r!=NULL)
        {
            printf("%c",temp.r->data);
            Q.queue[Q.tail++]=*temp.r;
        }
    }
    return 0;
}
int main()
{
    A* p;
    p=fun1();
    fun2(p);
    return 0;
}

这是第二题

问题 C: 二叉树的输入

描述

用二叉树的带虚结点表示的前序遍历序可以唯一的确定一棵二叉树。

格式

输入格式

输入包含多组数据。

每行是一棵二叉树的带虚结点（#）表示的前序遍历序串，长度不超过2000。每个结点为一个字符。

输出格式

对每行输入，输出对应二叉树的中序遍历序（不含虚结点）、后序遍历序（不含虚结点）和层次遍历序（不含虚结点）。

每棵二叉树的输出占一行，中序遍历序、后序遍历序和层次遍历序之间用一个空格隔开。

样例

样例输入 Copy

ab##c##

ab###

样例输出 Copy

bac bca abc

ba ba ab

代码如下

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct TREE)

struct TREE
{
    char data;
    struct TREE*l,*r;
};
typedef struct TREE A;

struct QUEUE
{
    A queue[20];
    int head,tail;
};
typedef struct QUEUE B;

A* fun()
{
    A* p;
    int x;
    scanf("%c",&x);
    if(x==EOF) exit(0);
    if(x=='#')
        p=NULL;
    else
    {
        p=(A*)malloc(LEN);
        p->data=x;
        p->l=fun();
        p->r=fun();
    }
    return p;
}
void fun1(A* p)
{
    if(p!=NULL)
    {
        fun1(p->l);
        printf("%c",p->data);
        fun1(p->r);
    }
}
void fun2(A* p)
{
    if(p!=NULL)
    {
        fun2(p->l);
        fun2(p->r);
        printf("%c",p->data);
    }
}

void fun3(A *p)
{
    A temp;
    if(p!=NULL)
    {
        B Q;
        printf("%c",p->data);
        Q.head=0,Q.tail=0;
        Q.queue[Q.tail++]=*p;
        while(Q.head!=Q.tail)
        {
            temp=Q.queue[Q.head++];
            if(temp.l!=NULL)
            {
                printf("%c",temp.l->data);
                Q.queue[Q.tail++]=*temp.l;
            }
            if(temp.r!=NULL)
            {
                printf("%c",temp.r->data);
                Q.queue[Q.tail++]=*temp.r;
            }
        }
    }

}
int main()
{
    freopen("input.txt","r",stdin);
    while(1)
    {
        A* p;
        p=fun();
        fun1(p);
        printf(" ");
        fun2(p);
        printf(" ");
        fun3(p);
        printf("\n");
        if(getchar()==EOF) exit(0);
    }
    return 0;
}

PS：这是迄今为止我写过的最长的代码了，开心，嘿嘿！！

秃头的7小时学习就这么结束了，不晚安，派大星。

秃头“种树”，“种树”秃头 2021-01-28