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

向右看齐 2022-12-21 04:57 117阅读 0赞

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

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

Input  
输入数据有多行，第一行是一个整数t (t<1000)，代表有t行测试数据。每行是一个长度小于50个字符的字符串。  
Output  
输出二叉树的层次遍历序列。  
Sample  
Input  
2  
abd,eg,cf,  
xnl,i,u,  
Output  
abcdefg  
xnuli

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        
        char data;
        struct node *left;
        struct node *right;
    };
    char a[150];
    int n;
    struct node *creat()//建树
    {
        
        struct node *root;
        if(a[n]==',')
        {
        
            root=NULL;
            n++;
        }
        else
        {
        
            root=(struct node *)malloc(sizeof(struct node));
            root->data=a[n];
            n++;
            root->left=creat();
            root->right=creat();
        }
        return root;
    };
    void cengxu(struct node *root)//层序遍历
    {
        
        struct node *temp[100];
        int in,out;
        in=out=0;
        temp[in++]=root;
        while(in>out)
        {
        
            if(temp[out])
            {
        
                printf("%c",temp[out]->data);
                temp[in++]=temp[out]->left;
                temp[in++]=temp[out]->right;
                /* 每次把这一层存入，然后输出的时候就把他的左右节点存入
                 * 例如一颗完全二叉树abcdefg（层序遍历顺序）  输出a的时候把bc放入,输出b的时候把b
                 * 的孩子放入也就是de，再输出c并且放入孩子fg，依次这样，达到层序的要求 
                */
            }
            out++;
        }
    }
    int main()
    {
        
        int t;
        scanf("%d",&t);
        while(t--)
        {
        
            n=0;
            scanf("%s",a);
            struct node *root;
            root=creat();
            cengxu(root);
            printf("\n");
        }
    }