二叉樹層次遍歷 - acm1314－IT工程師數位筆記本

文章出處

遺忘 --- 真是一件迷人的事兒。 ---- 某無恥樂觀的小逗比

// 題目： UVA 122  
/*
問題描述： 輸入一個二叉樹（如示例）。 （）空括號是一組輸入結束的標志 
要求輸出： 按從上到下， 從左到右的順序，輸出結點值。 即：層次遍歷。 
解決方案： 建樹 ----> bfs遍歷 
示例：
	 輸入：(3，L) (4,R) (5,) () 
	 輸出： 5 3 4
	 
	               5 
	             /   \
		    3     4  
*/

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <queue>
  4 #include <vector>
  5 #include <cstring>
  6 #include <fstream>
  7 using namespace std; 
  8 
  9 const int maxn = 1000 + 10; 
 10 
 11 // 二叉樹結構體 
 12 struct Node{
 13     bool have_value;             // 是否被賦值過 
 14     int v;                         // 節點值 
 15     Node *left, *right; 
 16     Node():have_value(false), left(NULL), right(NULL) {
 17     }                 // 構造函數  
 18 };
 19 
 20 char s[maxn]; // 保存讀入結點 
 21 int failed; 
 22 Node* root; 
 23 
 24 Node* newnode(); // 申請新結點 
 25 void remove_tree(Node* u); // 釋放樹 
 26 void addnode(int v, char * s); // 添加結點 
 27 bool read_input();                // 輸入 
 28 bool bfs(vector<int>& ans);     // BFS層次遍歷 
 29 
 30 
 31 int main()
 32 {
 33     vector<int> ans; 
 34     vector<int>::iterator it;
 35     while(read_input()) {
 36     if(!bfs(ans)) failed = 1;
 37     if(failed) printf("not complete\n");
 38     else {
 39       for(it = ans.begin(); it != ans.end(); it++)
 40       {
 41         if(it != ans.begin()) printf(" ");
 42         printf("%d", *it);
 43       }
 44       printf("\n");
 45     }
 46   }
 47     return 0;  
 48 } 
 49 
 50 Node* newnode() { return new Node(); }
 51 void remove_tree(Node* u)
 52 {
 53     if( u == NULL) return; 
 54     remove_tree(u->left); 
 55     remove_tree(u->right); 
 56     delete u; 
 57 }
 58 
 59 bool read_input(){
 60     failed = false; 
 61     root = newnode();         // 創建根結點
 62     for (;;)
 63     {
 64         if (scanf("%s", s) != 1) return false; // 整個輸入結束
 65         if (!strcmp(s, "()")) break;            // 讀到結束標志， 退出循環
 66         int v; 
 67         sscanf(&s[1], "%d", &v);                 // 讀入結點值
 68         addnode(v, strchr(s, ',') + 1);         // 查找逗號， 然后插入結點 
 69     }    
 70     return true; 
 71 }
 72 
 73 void addnode(int v, char *s)
 74 {
 75     int n = strlen(s); 
 76     Node* u = root;                     // 從根結點開始往下走 
 77     for (int i = 0; i < n; i++)
 78         if(s[i]=='L')
 79         {
 80             if(u->left==NULL)            // 結點不存在 
 81                 u->left = newnode();     // 建立新結點 
 82             u = u->left;                 // 往左走 
 83         }
 84         else if(s[i]=='R')
 85         {
 86             if (u->right == NULL)
 87                 u->right = newnode(); 
 88             u = u->right; 
 89         }                                // 忽略其他情況， 即最后那個右括號 
 90         if(u->have_value) failed = true; // 已經賦過值， 表明輸入有誤 
 91         u->v = v; 
 92         u->have_value = true;                 // 小心， 別忘記做標記 
 93 }
 94 
 95 bool bfs(vector<int>& ans)
 96 {
 97     queue<Node*> q;                        // 初始時只有一個根結點 
 98     ans.clear(); 
 99     q.push(root); 
100     while(!q.empty())
101     {
102         Node* u = q.front(); q.pop(); 
103         if(!u->have_value) return false; // 有結點沒有被賦值過， 表明輸入有誤。  
104         ans.push_back(u->v);                 // 增添到輸出隊列尾部 
105         if(u->left != NULL) q.push(u->left);     // 把左子結點（如果有）放進隊列 
106         if(u->right != NULL) q.push(u->right);     // 把右子結點（如果有）放進隊列 
107     }
108     return true;                     // 輸入正確 
109 }