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

叁歲伎倆 2022-04-18 03:20 112阅读 0赞

Problem Description

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

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

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

abd,eg,cf,  
xnl,i,u,  
Sample Output

dfg  
uli

#include <stdio.h>
    #include <stdlib.h>
    
    struct node
    {
        char data;
        struct node * l;
        struct node * r;
    };
    
    char a[100];
    int n;
    
    struct node * create()
    {
        struct node * root;
        if(a[n] == ',')
        {
            n++;
            root = NULL;
        }
        else
        {
            root = (struct node * )malloc(sizeof(struct node));
            root->data = a[n];
            n++;
            root->l= create();
            root->r= create();
        }
        return root;
    };
    
    void yezi(struct node * root)
    {
        struct node * t[100];
        int in = 0, out = 0;
        t[in] = root;
        in++;
        while(in > out)
        {
            if(t[out])
            {
                if(t[out]->l==NULL&&t[out]->r==NULL)
                {
                    printf("%c",t[out]->data);
                }
               if(t[out]->l!=NULL)
                {
                    t[in++] = t[out]->l;
                }
               if(t[out]->r!=NULL)
                {
                  t[in++] = t[out]->r;
                }
            }
            out++;
        }
    }
    
    int main()
    {
        struct node * root;
        while(scanf("%s",a)!=EOF)
        {
            n= 0;
            root = create();
            yezi(root);
            printf("\n");
        }
        return 0;
    }