题目：

Trees are fundamental in many branches of computer science (Pun definitely intended). Current stateof-the
art parallel computers such as Thinking Machines’ CM-5 are based on fat trees. Quad- and
octal-trees are fundamental to many algorithms in computer graphics.
This problem involves building and traversing binary trees.
Given a sequence of binary trees, you are to write a program

that prints a level-order traversal of each tree. In this problem each node of a binary tree contains a positive integer and all binary trees have have fewer than 256 nodes. In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k + 1.

For example, a level order traversal of the tree on the right is: 5, 4, 8, 11, 13, 4, 7, 2, 1.
In this problem a binary tree is specified by a sequence of pairs ‘(n,s)’ where n is the value at the node whose path from the root is given by the string s. A path is given be
a sequence of ‘L’s and ‘R’s where ‘L’ indicates a left branch and ‘R’ indicates a right branch. In the
tree diagrammed above, the node containing 13 is specified by (13,RL), and the node containing 2 is
specified by (2,LLR). The root node is specified by (5,) where the empty string indicates the path from
the root to itself. A binary tree is considered to be completely specified if every node on all root-to-node
paths in the tree is given a value exactly once.

Input
The input is a sequence of binary trees specified as described above. Each tree in a sequence consists
of several pairs ‘(n,s)’ as described above separated by whitespace. The last entry in each tree is ‘()’.
No whitespace appears between left and right parentheses.
All nodes contain a positive integer. Every tree in the input will consist of at least one node and
no more than 256 nodes. Input is terminated by end-of-file.

Output
For each completely specified binary tree in the input file, the level order traversal of that tree should
be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a
node is given a value more than once, then the string ‘not complete’ should be printed.
Sample Input
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
Sample Output
5 4 8 11 13 4 7 2 1
not complete

思路：

这题是大概意思是给出一些数据,让你创建一棵二叉树，并按层次遍历的顺序输出结果，如果给出的数据有误，则输出“not complete”。如样例输入(11,LL)的意思的在根节点的左孩子的左孩子的值是11。

这道题的难点在于怎么处理输入的数据。层次遍历不难，其实就是宽度优先搜索。

我利用了C语言的库函数atoi()来转换数字。其实有很多种方法可以实现。

接下来就是创建树的问题了。代码里有详细的注释，我就不多说了。

代码：

#include <iostream>
#include <cstdlib>
#include <string>
#include <queue>
#include <vector>
/* *编译环境：CodeBlocks mingw32-g++ STL11标准 *mingw32-g++.exe -Wall -fexceptions -g -std=c++11 */
using namespace std;

const int INF = 1000000000;//当输入为诸如(,LLR)这种错误情况时，用 -INF 表示这种错误
struct tag_TreeNode//树节点
{
    int data;
    bool haveValue, error;//haveValue->是否曾经被赋值 ,error->是否被重复赋值或者是否输入没有给出值
    struct tag_TreeNode * leftChild, *rightChild;
    tag_TreeNode() { data = 0; haveValue = error = false; leftChild = rightChild = nullptr; }
};

typedef struct tag_TreeNode TreeNode;

struct tag_data
{
    int data;
    string message;//节点位置信息
}Data[260];//用来暂时存储输入的数据

struct tag_data deal(string& s)//此函数用来处理输入的数据
{
    struct tag_data data;
    auto pos = s.find(',');//如果pos==1，则说明输入的数据有误，如(,LLR)这种情况，数据没有给出值
    if (pos != 1)data.data = atoi(s.substr(1, pos).c_str());
    else  data.data = -INF;//前面已经说过，用 -INF 表示这种错误
    data.message = s.substr(pos + 1);//节点位置信息（特意删去后面的半个括号纯属多此一举，所以这里不删）
    return data;
}

void CreateTree(struct tag_data d[], const int n,  TreeNode *root)//创建一棵树
{
    for (int i = 1; i <= n; i++) {//遍历所有被处理过的数据
        TreeNode* u = root;//每次都从根节点出发，根据处理后的数据查找节点位置，并进行处理
        for (size_t j = 0; j < d[i].message.length(); j++) {//遍历节点位置信息，寻找位置
            if (d[i].message[j] == 'L') {//去左子树
                if (u->leftChild == nullptr) u->leftChild = new TreeNode();//左子树为NULL则创建左子树
                u = u->leftChild;
            }
            else if (d[i].message[j] == 'R') {//去右子树
                if (u->rightChild == nullptr) u->rightChild = new TreeNode();
                u = u->rightChild;
            }
        }
        if (u->haveValue || d[i].data == -INF) u->error = true;//如果曾经被赋值或者输入的数据没有给出节点的值，则数据有误
        u->data = d[i].data;
        u->haveValue = true;//记得做这个标记
    }
}

bool  bfs( TreeNode  *root, vector<int> & v )//宽度优先搜索
{
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode  * p = q.front();
        q.pop();
        if (!p->haveValue || p->error) return false;//发现错误则返回false
        v.push_back(p->data);
        if (p->leftChild != nullptr) q.push(p->leftChild);
        if (p->rightChild != nullptr) q.push(p->rightChild);
    }
    return true;
}

void removeTree(TreeNode  *p)//后序遍历删除整颗树
{
    if (p == nullptr) return;
    if (p->leftChild) removeTree(p->leftChild);
    if (p->rightChild) removeTree(p->rightChild);
    delete p;
}

int main()
{
    TreeNode *root;
    string mes;
    int nodeNum = 0;//记录一组数据有多少个数据元素
    vector<int> v;//用来存放按层次遍历（其实就是宽搜。。。）所获得的值的顺序结果

    while (cin >> mes ) {
         if (mes!="()")Data[++nodeNum] = deal(mes);
         if (mes == "()") {//当遇到“()”时说明这组数据输入完毕，开始处理
             v.clear();//这一步和后面的清除整颗树这两个步骤不能少
             root = new TreeNode();
             CreateTree(Data, nodeNum, root);
             nodeNum = 0;
             if (!bfs(root,v))cout << "not complete" << endl;
             else {
                 for (size_t i = 0; i < v.size(); i++) {
                     if (i)   cout << " " << v[i];
                     else cout << v[i];
                 }
                 cout << endl;
             }
             removeTree(root);//必不可少的步骤
         }
     }
    return 0;
}

本来我的想法是在宽搜的时候就输出结果，结果“WrongAnswer”了，调试发现这样做的话，在没有遇见数据有误的节点时它会正常输出，当遇到有问题的数据如某组数据中有（,LLR）时就输出了”5 11not complete”之类数字加字符串的结果。。。
这是个坑。。。所以不要这么干。用个vector存起来也没耗多少内存和时间。