数据结构实验之二叉树七：叶子问题(二叉树+队列)

桃扇骨 2022-07-12 02:20 83阅读 0赞

[sdut原题链接][sdut]

数据结构实验之二叉树七：叶子问题  
Time Limit: 1000MS Memory Limit: 65536KB

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

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

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

Example Input  
abd,,eg,,,cf,,,  
xnl,,i,,u,,

Example Output  
dfg  
uli

Hint  
二叉树+队列  
Author  
xam

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    typedef struct node
    {
        char date;
        struct node *left;
        struct node *right;
    }BinTree;
    BinTree *root;
    BinTree *link[54];
    char s[54];
    int flag, pu, po;
    BinTree * creat()
    {
        BinTree *root;
        if(s[flag++] == ',')
            root = NULL;
        else
        {
            root = (BinTree *)malloc(sizeof(BinTree));
            root->date = s[flag-1];
            root->left = creat();
            root->right = creat();
        }
        return root;
    }
    void put_leave(BinTree *root)
    {
        if(root)
        {
            pu = po = 0;
            link[pu++] = root;
            while(pu > po)
            {
                if(!link[po]->left && !link[po]->right)
                {
                    printf("%c", link[po]->date);
                }
                if(link[po]->left)
                {
                    link[pu++] = link[po]->left;
                }
                if(link[po]->right)
                {
                    link[pu++] = link[po]->right;
                }
                po++;
            }
        }
    }
    int main()
    {
        while(scanf("%s", s) != EOF)
        {
            flag = 0;
            root = creat();
            put_leave(root);
            printf("\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name:
    Result: Accepted
    Take time: 0ms
    Take Memory: 116KB
    Submit time: 2017-02-07 16:09:24
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2005/pid/3346