二叉树层次遍历

遗忘 --- 真是一件迷人的事儿。 ---- 某无耻乐观的小逗比

// 题目： 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
");
 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("
");
 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 }

Talk is cheap, Reading is cheap. Just do it!