SDUTOJ 3344 数据结构实验之二叉树五：层序遍历（树与队列）

数据结构实验之二叉树五：层序遍历

Problem Description

已知一个按先序输入的字符序列，如abd,eg,cf,(其中,表示空结点)。请建立二叉树并求二叉树的层次遍历序列。

Input

输入数据有多行，第一行是一个整数t (t<1000)，代表有t行测试数据。每行是一个长度小于50个字符的字符串。

Output

输出二叉树的层次遍历序列。

Sample Input

2
abd,eg,cf,
xnl,i,u,

Sample Output

abcdefg
xnuli

我们已经学会了二叉树的先序遍历，中序遍历，后续遍历。现在我们再来学习二叉树的层序遍历。
首先要明确什么是层序遍历：
通俗点就是从上到下，从左到右依次输出整个树。
比如这颗树：

层次遍历为：A BC DFGI EH

理解了怎么输出，那么我们如何具体实现呢？
答案是：通过队列实现。
遍历从根节点开始，首先将根节点入队，然后开始执行循环：节点出队，访问该节点，其左右儿子入队。

下面做图辅助理解。

首先将A放入队列。

然后A出列输出，其左右儿子BC入队。

然后B出列输出，其左右儿子DF入列

然后C出列输出，其左右儿子GI入列。

然后D出列，其左右儿子…没有！ 所以不需要入列。

然后F出列，其左右儿子，只有一个E 入列。

好了，后面的依次类推。

给出代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
    char date;
    struct node *l, *r;
} tree;

int i;
tree *queue[55];  // 构建指针队列
int in = 0;
int out = 0;

tree *creat( char a[] );
void show( tree *root );

int main()
{
    char a[55];
    int pp,list;
    scanf("%d",&list);
    for ( pp=0; pp<list; pp++ ) {
        scanf("%s",a);

        tree *root;
        root = (tree *)malloc(sizeof(tree));

        i = 0, in = 0, out = 0;
        root = creat(a);
        show(root);

        printf("\n");
    }

    return 0;
}

tree *creat( char a[] ) //构建树
{
    tree *p;
    p = (tree *)malloc(sizeof(tree));

    if ( a[i++]==',' ) {
        return NULL;
    } else {
        p -> date = a[i-1];
        p -> l = creat(a);
        p -> r = creat(a);
    }

    return p;
}

void show( tree *root )
{
    queue[in++] = root;
    while ( in>out ) {
        if ( queue[out] ) {
            printf("%c",queue[out]->date);
            queue[in++] = queue[out]->l;
            queue[in++] = queue[out]->r;
        }
        out ++;
    }
}


/***************************************************
User name: rj180323石旭
Result: Accepted
Take time: 0ms
Take Memory: 164KB
Submit time: 2019-01-22 09:14:56
****************************************************/