這題的思路：讀入--》判斷是否為循環(huán)結(jié)束的條件（主動）--》判斷是否
輸入錯誤--》用隊列向vector中輸入合法數(shù)據(jù)--》按順序輸出

a)        編寫readin函數(shù)，專門用來讀取數(shù)據(jù)。函數(shù)返回類型為bool，輸入不合法時返回false。依題意，如果輸入只有()，表示input終止，跳出循環(huán)并返回true

b)        編寫名為Node的結(jié)構(gòu)體。結(jié)構(gòu)體中包含input中括號左側(cè)的結(jié)值、判斷結(jié)點是否被賦值的bool類型的值，和類型為Node *的左右子結(jié)點。由于二叉樹是遞歸定義的，其左右子結(jié)點類型都是“指向結(jié)類型的指針”，因此左右子結(jié)點的類型都是Node *

c)        建立全局變量failed，記錄是否有從根到某個葉結(jié)的路徑上有的結(jié)沒有在輸入中給出或值給出超過一次的情況

d)        建立函數(shù)addnode：按照移動序列走，目標不存在時調(diào)用newnode函數(shù)來創(chuàng)造新結(jié)點，判斷結(jié)點是否已被賦值（如果已經(jīng)被賦過值，將failed值改為true），并將結(jié)點值賦給對應(yīng)的結(jié)點

e)        bfs找結(jié)點，使用隊列：初始時只有一個根結(jié)點，然后每次取出一個結(jié)點，把它的左右子結(jié)點（如果存在）放進隊列中，用vector保存結(jié)點的值

PS:failed 僅僅是作為continue的條件 真正退出的條件只能是readin讀入到了結(jié)束
failed在外部函數(shù)中出現(xiàn)在了readin里的addnode函數(shù)里 作為重復(fù)賦值的判斷
然后在bfs里有一個是否complete的判斷 也與failed一樣作為能否進入為vector賦值的條件

readin—》addnode—》bfs—》over

include<vector>

include<cstdio>

include<queue>

include<iostream>

include<cstring>

using namespace std;

const int maxn = 256 + 10;
char s[maxn];
bool failed;

struct Node{
int v; //結(jié)點值
bool have_value; //用來判斷是否被賦值過
Node *left, *right; //遞歸定義 左右結(jié)點
};
Node *root;

Node *newnode(){
return new Node(); //每建立一個結(jié)點 用new運算符申請
}

void addnode(int v,char *s){
Node *u = root; //將根節(jié)點指向的地址賦給u進行儲存
int n = strlen(s); //確定循環(huán)次數(shù)
for(int i = 0; i < n; n++){
if(s[i] == 'L'){
if(u->left==NULL){ //如果這個結(jié)點未被創(chuàng)建
u->left = newnode();//那么創(chuàng)建它
u = u->left; //并且將u指向它以進行下一次循環(huán)
}
}
else if(s[i] == 'R'){
if(u->right==NULL){ //同上
u->right=newnode();
u = u->left;
}
}
if(u->have_value) failed = true;//如果它已經(jīng)被創(chuàng)建 那么把標記值賦為ture 以在主函數(shù)中終止此次循環(huán)
u->v=v; //將值賦給新創(chuàng)建的結(jié)點
u->have_value=true; //并做標記，表示該結(jié)點已經(jīng)賦過值
}
}

void remove_tree(Node* u) {
if(u == NULL) return;
remove_tree(u->left);
remove_tree(u->right);
delete u;
}

bool readin(){ //這個函數(shù)是用來讀入的
failed = false;
remove_tree(root);
root = newnode(); //創(chuàng)建根結(jié)點 可能導(dǎo)致內(nèi)存泄漏
for( ; ; ){
if(scanf("%s", s) != 1) return false;//讀到了結(jié)束標志
if(strcmp(s,"()")) break;//比較字符串是否相等
//按照順序比，第一個都是T 第二個都是h 第三個a<e 所以...就這樣。比較方法就是挨個比較，利用ASCII碼
//相等返回0 大于返回正整數(shù) 小于返回負整數(shù)
int v;
sscanf(&s[1],"%d",&v); //不管了...
addnode(v,strchr(s,',')+1);//不管 看不懂
}
return true ;
}

bool bfs(vector<int>&ans){
queue<Node*> q; //創(chuàng)建隊列以存放結(jié)點
q.push(root); //將已經(jīng)創(chuàng)建好的樹的根節(jié)點放入隊列
while(!q.empty()){ //當隊列不為空（即未全部按順序加入vector完）
Node *u = q.front(); //創(chuàng)建結(jié)構(gòu)指針 指向隊列頭
q.pop(); //出列
if(!u->have_value) return false;//如果該結(jié)點未被賦值過 則樹不完整 返回false 在主函數(shù)中結(jié)束此次循環(huán)
if(u->left!=NULL) q.push(u->left); //若不為空 則加入隊列中
if(u->right!=NULL) q.push(u->right);//注意先左再右（題目要求）
}//有些樹可能have_value是空的 但是仍為一些結(jié)點的根節(jié)點
return true;
}

int main(){
while(1){
if(!readin()) break;

    vector<int>ans;
    if(!failed&&bfs(ans)){
        int len = ans.size();
        for(int i = 0; i < len; i++){
            printf("%d%c",ans[i],i == len-1?'\n':' ');
        }
    }
    else 
        printf("not complete");
}
return 0;

}