九度oj 1523 从上往下打印二叉树

原题链接：http://ac.jobdu.com/problem.php?pid=1523

建树，再层次遍历bfs。为了找根方便些，加了father指针。。。

如下：

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 using std::queue;

 using std::vector;

 using std::cin;

 const int Max_N = ;

 struct Node{

     int v;

     Node *f, *ch[];

     inline void set(int _v = , Node *p = NULL){

         v = _v, f = ch[] = ch[] = p;

     }

     inline void link(Node *x, bool d){

         ch[d] = x;

         x->f = this;

     }

 };

 struct BinaryTree{

     Node *tail, *root, *null;

     Node stack[Max_N], *ptr[Max_N];

     void init(){

         tail = &stack[];

         null = tail++;

         null->set();

         root = null;

     }

     inline Node *newNode(int v){

         Node *p = tail++;

         p->set(v, null);

         return p;

     }

     inline void gogo(int n){

         char c;

         int i, v, a, b;

         for (i = ; i <= n; i++){

             scanf("%d", &v);

             ptr[i] = newNode(v);

         }

         for (i = ; i <= n; i++){

             cin >> c;

             if (c == 'd'){

                 scanf("%d %d", &a, &b);

                 ptr[i]->link(ptr[a], );

                 ptr[i]->link(ptr[b], );

             } else if (c == 'l'){

                 scanf("%d", &a);

                 ptr[i]->link(ptr[a], );

             } else if (c == 'r'){

                 scanf("%d", &b);

                 ptr[i]->link(ptr[b], );

             } else {

                 ;

             }

             if (ptr[i]->f == null) root = ptr[i];

         }

     }

     inline void bfs(){

         queue<Node *> que;

         vector<int> ans;

         que.push(root);

         while (!que.empty()){

             Node *x = que.front();

             que.pop();

             ans.push_back(x->v);

             if (x->ch[] != null) que.push(x->ch[]);

             if (x->ch[] != null) que.push(x->ch[]);

         }

         int n = ans.size();

         for (int i = ; i < n; i++){

             printf("%d%c", ans[i], i < n -  ? ' ' : '\n');

         }

     }

 }tree;

 int main(){

 #ifdef LOCAL

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w+", stdout);

 #endif

     int n;

     while (~scanf("%d", &n)){

         tree.init(), tree.gogo(n), tree.bfs();

     }

     return ;

 }