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

seven_ • 2023年2月21日下午10:13 • Python • 阅读 340

二叉树的层次遍历

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

题目是不难的，但是犯了一个小错误，记录一下吧。

#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<iostream>
using namespace std;
string str;
int pos = 0;
typedef struct node{
    char data;
    struct node * left;
    struct node * right;
}Node, *Tree;
void Create(Tree &T){
        char ch = str[pos++];
        if(ch == ',')
            T = NULL;
        else{
            T = (Tree)malloc(sizeof(Node));
            T->data = ch;
            Create(T->left);
            Create(T->right);
        }
}
void Level(Tree T){
    queue<Tree> que;
    if(T){
        que.push(T);      //注意一定要判断再入队列，要不然只输入一个,的时候会崩
    }
    while(!que.empty()){
        Tree temp = que.front();
        que.pop();
        cout<<temp->data;
        if(temp->left)
            que.push(temp->left);
        if(temp->right)
            que.push(temp->right);
    }
}
int main(){
    int n;
    cin>>n;
    while(n--){
        cin>>str;
        Tree t;
        pos = 0;
        Create(t);
        Level(t);
        cout<<endl;
    }
    return 0;
}