【日常学习】【指针二叉树+BFS】Uva - 122 Trees on the level题解

柔情只为你懂 2022-08-07 04:51 11阅读 0赞

作为一个传统型的树盲，不得不把树重新学习一次。通常我是不太喜欢指针的，但这样写下来感觉还能接受。

题目来源是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 &试一下传引用是否可以，事实上可以AC
    	if (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 address
    	int 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;
    }

今天看了自主招生各项资料，真的亚历山大。下一步要稍稍跟一根生物和化学，生物奥赛拿奖希望渺茫，但是我还是想试一下；化学我觉得还是有点希望过初赛的【众人：才过初赛你还敢在这儿嚷嚷】好吧我自以为略略有些有机的底子，补补蓝皮和邢大本说不定混个二等？【众：你把二等当什么了！】好吧混个三等···好吧至少过初赛···好吧还是得拼裸分啊啊啊，加油吧···路漫漫其修远兮，为伊消得人憔悴，虽石烂海枯，而此身尚存，此心不死。既不可以失败而灰心，亦不能以困难而缩步。精神贯注，猛力向前，应付世界进步之潮流，合乎善长恶消之天理，则终有最后成功之一日。（我都写了些什么···

——风萧萧兮易水寒，壮士一去兮不复还