数据结构实验之二叉树七：叶子问题

约定不等于承诺〃 2024-02-18 22:32 30阅读 0赞

#### 数据结构实验之二叉树七：叶子问题 ####

Time Limit: 1000 ms Memory Limit: 65536 KiB

[Submit][] [Statistic][]

Problem Description

已知一个按先序输入的字符序列，如abd,,eg,,,cf,,,(其中,表示空结点)。请建立该二叉树并按从上到下从左到右的顺序输出该二叉树的所有叶子结点。

Input

输入数据有多行，每一行是一个长度小于50个字符的字符串。

Output

按从上到下从左到右的顺序输出二叉树的叶子结点。

Sample Input

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

Sample Output

dfg
    uli

Hint

Source

xam

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    char a[101];
    int l;
    struct node//二叉树的定义
    {
        char data;
        struct node *lc;
        struct node *rc;
    };
    struct node *creat()
    {
        struct node *root;
        char c;
        c = a[l++];
        if(c == ',')
        {
            return NULL;
        }
        else
        {
            root = (struct node *)malloc(sizeof(struct node));
            root->data = c;
            root->lc = creat();
            root->rc = creat();
        }
        return root;
    }
    void cengci(struct node *root)
    {
        int out = 0, in = 0;
        struct node *q[100];
        q[in++] = root;
        while(in > out)
        {
            if(q[out] != 0)
            {
                if(q[out]->lc == NULL && q[out]->rc == NULL)
                    printf("%c", q[out]->data);
                q[in++] = q[out]->lc;
                q[in++] = q[out]->rc;
            }
            out++;
        }
    }
    int main()
    {
        struct node *root;
        int i, j, m, n, k, t;
        while(scanf("%s", a) != EOF)
        {
            root = (struct node *)malloc(sizeof(struct node));
            l = 0;
            root = creat();
            cengci(root);
            printf("\n");
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2562/pid/3346.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2562/pid/3346.html