這題的思路：讀入--》判斷是否為循環(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;
}
