秃頭“種樹”，“種樹”秃頭 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