【紫书】Trees on the level UVA - 122 动态建树及bfs

题意：给你一些字符串，代表某个值被插入树中的位置。让你输出层序遍历。

题解：动态建树。

　　　由于输入复杂，将输入封装成read_input。注意输入函数返回的情况

　　　再将申请新节点封装成newnode().

　　　最后层序输出直接用bfs实现。

坑：我把ans.clear放到主程序的if里面，导致某特定情况无法初始化，wa了一页//以后debug真的别XJB改细节了上下语句顺序，一些无关紧要的处理，改之前想一想

#define _CRT_SECURE_NO_WARNINGS

#include "stdio.h"

#include<stdio.h>

#include<algorithm>

#include<string>

#include<vector>

#include<list>

#include<set>

#include<iostream>

#include<string.h>

#include<queue>

using namespace std;

const int maxn = ;

char s[maxn];

int failed;

struct node {

    int v;

    bool have_v;

    node* leftson, *rightson;

    node() :have_v(false), leftson(NULL), rightson(NULL) {}

}*root;

node* newnode() { return new node(); }

void addnode(int v, char *s) {

    int n = strlen(s);

    node * now = root;

    for (int i = ; i < n - ; i++) {

        if (s[i] == 'L') {

            if (now->leftson == NULL) now->leftson = newnode();

            now = now->leftson;

        }

        else {

            if (now->rightson == NULL) now->rightson = newnode();

            now = now->rightson;

        }

    }

    if (now->have_v) { failed = ; }

    now->v = v;

    now->have_v = ;

}

bool read_input() {

    failed = false; root = newnode();

    while () {

        while (scanf("%s", &s) != )return false;

        if (s[] == ')')break;

        int v;

        sscanf(&s[], "%d", &v);

        addnode(v, strchr(s, ',') + );

    }

    return true;

}

list<int>ans;

void bfs() {

    ans.clear();

    queue<node> Q;

    node now;

    //int vis[maxn];

    Q.push(*root);

    while (!Q.empty()) {

        now = Q.front(); if (!now.have_v) { failed = ; break; }

        Q.pop();

        if (now.leftson != NULL)Q.push(*now.leftson);

        if (now.rightson != NULL)Q.push(*now.rightson);

        ans.push_back(now.v);

    }

}

int main() {

    while (read_input()) {

        bfs();

        if (failed)cout << "not complete" ;

        else

        {

            cout << ans.front(); ans.pop_front();

            for (auto t : ans)cout << ' ' << t;

        }

        cout << endl;

    }

    system("pause");

}