題意：給出一棵二叉樹，按照從上到下，從左到右輸出所有節點的值，如果有一個節點沒有賦值或者被多次賦值則輸出not complete

看的紫書照著敲的= = 先要將輸入進來的值建成一顆二叉樹（定義一個二叉樹的節點，新建節點的函數，添加節點的函數），再對建好的二叉樹遍歷(BFS)

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<vector> 6 #include<queue> 7 #include<algorithm> 8 using namespace std; 9 10 typedef long long LL; 11 const int maxn=10000+5; 12 char s[maxn]; 13 int failed; 14 vector<int> ans; 15 16 struct Node{ //建立二叉樹的一個結點 17 bool have_value;//判斷該結點是否被賦值過 18 int v; 19 Node *left,*right; 20 Node():have_value(false),left(NULL),right(NULL){}//構造函數，即為賦初值 21 }; 22 23 Node*root; 24 Node* newnode() { //創建一個新的結點 25 return new Node(); 26 } 27 28 void addnode(int v,char *s){ //添加一個新的 結點 29 int n=strlen(s); 30 Node* u=root; 31 for(int i=0;i<n;i++) 32 if(s[i]=='L'){ 33 if(u->left==NULL) u->left=newnode();//如果左邊的結點不存在，建立新的結點 34 u=u->left; //向左走 35 } 36 else if(s[i]=='R'){ 37 if(u->right==NULL) u->right=newnode();//如果右邊的結點不存在，建立新的結點 38 u=u->right;//向右走 39 } 40 if(u->have_value) failed=true; //如果已經賦過值 ，輸入有誤 41 u->v=v;//標記 42 u->have_value=true; 43 } 44 45 bool read_input(){ 46 failed=false; 47 root=newnode(); 48 for(;;){ 49 if(scanf("%s",&s)!=1) return false; 50 if(!strcmp(s,"()")) break; 51 int v; 52 sscanf(&s[1],"%d",&v); 53 addnode(v,strchr(s,',')+1); 54 } 55 return true; 56 } 57 58 59 60 61 bool bfs(vector<int>& ans){ 62 queue<Node*> q; 63 ans.clear(); 64 q.push(root); 65 while(!q.empty()){ 66 Node* u=q.front();q.pop(); 67 if(!u->have_value) return false;//有結點沒有被賦值，輸出有誤 68 ans.push_back(u->v);//增加到輸出序列尾部 69 if(u->left!=NULL) q.push(u->left);//如果存在左子結點，放進隊列 70 if(u->right!=NULL) q.push(u->right);// 如果存在右子結點，放進隊列 71 } 72 return true; 73 } 74 75 int main() 76 { 77 int i; 78 while(read_input()){ 79 if(failed||!bfs(ans)) printf("not complete\n"); 80 else{ 81 for(i=0;i<ans.size()-1;i++) 82 printf("%d ",ans[i]); 83 printf("%d\n",ans[i]); 84 } 85 } 86 return 0; 87 } View Code

?

?

?

?

?

?

?

?

數據結構學得好艱辛啊啊啊啊啊= =

轉載于:https://www.cnblogs.com/wuyuewoniu/p/4324629.html

總結

以上是生活随笔為你收集整理的UVa 122 Trees on the level的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。