作为一个传统型的树盲，不得不把树重新学习一次。通常我是不太喜欢指针的，但这样写下来感觉还能接受。
题目来源是ACM DUKE 1993 Uva 122 杭电也有这道题 这道题目基本是照着ruka抄来的，Uva这两天天天上不去，华科的VJ也没法用，与使用杭电测了一下
第一次在Uva测的时候，奇怪的WA了，在杭电测是PE（我人生中第一个PE···），然后才发现换行符输出的位置错了，我在最后一个else里没有加块 直接导致输出完毕not complete后会连着输出两个换行符。Uva好像没有PE这样可喜可贺的东西啊。
题目刚开始我根本不知如何下手，ruka的思路是先用字符串读入，再从字符串中读数字；递归建立指针链表，每一个L就开一个新的指针left，在读入过程中不判重，程序运行过程中用failed判重和判断是否为空。整个程序结构和思路非常清晰。
学习到的一点语法小贴士：
1.对于指针变量a,a->x就是*a.x 前星后点 不如箭头简单
2.指针的定义，Node *left,*right 刚开始里奥告诉我Node* 后面就不用加星号 但如果直接Node 后面每个变量都要加星号 但是尝试了一下发现只能在每个变量前都加星号。
3.不得不深深佩服ruka君，代码简洁明了，结构非常清晰，主程序中写思路，用到一个程序就写一个块。我要学习这种做法。
那么，放代码
//Uva 122 Duke 1993 Trees on the level//link list struct#include<cstdio>#include<cstring>#include<queue>#include<vector>using namespace std;bool failed;struct Node{bool have_value;int v;Node *left,*right;//递归构建指针链表二叉树Node():have_value(false),left(NULL),right(NULL){}//构造函数，析构函数如果不写由程序默认提供，注意构造函数只能通过new使用，析构函数是delete};Node* root;Node* newnode(){return new Node();//申请新空间，同时调用构造函数初始化}void remove_tree(Node* u){//just try &试一下传引用是否可以，事实上可以ACif (u==NULL) return;//提前判断remove_tree(u->left);//递归释放空间remove_tree(u->right);delete u;//析构}void addnode(int v,char* s){//in fact char* is a string,it's the first char's addressint n=strlen(s);Node* u=root;//从根往下for (int i=0;i<n;i++){//if it's NULL it won't run this step如果是空的，不会走这一步，但这样不是错误if (s[i]=='L'){if (u->left==NULL) u->left=newnode();//节点不存在就建立新的，否则往下走u=u->left;}else if (s[i]=='R'){if (u->right==NULL) u->right=newnode();u=u->right;}}if (u->have_value) failed=true;//已赋过值，打标记u->v=v;u->have_value=true;}char s[300];bool read_input(){//while reading do not check legitimacy读入函数，读入时不检查是否有误，但每次读入重新设定布尔变量初值failed=false;remove_tree(root);//清空树，释放空间（析构函数）root=newnode();//创建根节点，此处调用构造器初始化（构造函数）for (;;){if (scanf("%s",s)!=1) return false;//整个读入结束if (!strcmp(s,"()")) break;//strcmp函数，比较两个串，s1<s2返回负，相等为0，大于为正，注意返回值不一定int v;sscanf(&s[1],"%d",&v);//sscanf是已经读入了c串s，然后从s中读入，输入源由键盘变成了c字符串，，以%d形式读到v中，注意c字符串把任意指向字符的指针看做字符串的起始位置，因此这里相当于是读入了从字符串第二位开始的新串addnode(v,strchr(s,',')+1);//查找逗号，返回逗号的指针+1}return true;}bool bfs(vector<int>& ans){//传引用queue<Node*> q;ans.clear();//初始化q.push(root);//初始只有根while (!q.empty()){Node* u=q.front();q.pop();//每次读取头元素并出队if (!u->have_value) return false;//没有赋过值，说明错误ans.push_back(u->v);if (u->left !=NULL) q.push(u->left);if (u->right !=NULL) q.push(u->right);}return true;}int main(){vector<int> ans;while (read_input()){if (!bfs(ans)) failed=1;if (failed) printf("not complete\n");else{for (int i=0;i<ans.size();i++){if (i!=0) printf(" ");printf("%d",ans[i]);}printf("\n");}}return 0;}今天看了自主招生各项资料，真的亚历山大。下一步要稍稍跟一根生物和化学，生物奥赛拿奖希望渺茫，但是我还是想试一下；化学我觉得还是有点希望过初赛的【众人：才过初赛你还敢在这儿嚷嚷】好吧我自以为略略有些有机的底子，补补蓝皮和邢大本说不定混个二等？【众：你把二等当什么了！】好吧混个三等···好吧至少过初赛···好吧还是得拼裸分啊啊啊，加油吧···路漫漫其修远兮，为伊消得人憔悴，虽石烂海枯，而此身尚存，此心不死。既不可以失败而灰心，亦不能以困难而缩步。精神贯注，猛力向前，应付世界进步之潮流，合乎善长恶消之天理，则终有最后成功之一日。（我都写了些什么···
——风萧萧兮易水寒，壮士一去兮不复还
才会看到属于自己的那一片晴朗的天空。
