SOJ 1156. Binary tree

题目大意：输入整数n，代表n个树结点，接着输入n个树结点的信息，每行代表个一个结点，包括四个元素：结点编码，携带的信息（字符），左儿子，右儿子。要求模拟先序遍历，输出结点信息。

解题思路：新建结构体Node，包含携带信息，左儿子和右儿子等信息。Node[i]即代表编号为i的结点。判断树的根节点，从根节点进行先序遍历。

代码如下：

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 const int maxn = 10005;
 6 
 7 struct Node {
 8     // int i;
 9     char ch;
10     int l;
11     int r;
12     /*Node(int i_ = 0, char ch_ = '', int l_ = 0, int r_ = 0) {
13         i = i_;
14         ch = ch_;
15         l = l_;
16         r = r_;
17     }*/
18 };
19 
20 bool child[maxn];
21 vector<int> vt;
22 Node nodes[maxn];
23 
24 void init() {
25     for (int i = 0; i < maxn; i++) {
26         child[i] = false;
27     }
28     vt.clear();
29 }
30 
31 void preorder_search(int root) {
32     cout << nodes[root].ch;
33 
34     if (nodes[root].l != 0) preorder_search(nodes[root].l);
35     if (nodes[root].r != 0) preorder_search(nodes[root].r);
36 }
37 
38 int main() {
39     int n;
40     while (cin >> n) {
41         init();
42         int ni, nl, nr;
43         char nch;
44         for (int i = 0; i < n; i++) {
45             cin >> ni >> nch >> nl >> nr;
46             vt.push_back(ni);
47             nodes[ni].ch = nch;
48             nodes[ni].l = nl;
49             nodes[ni].r = nr;
50             child[nl] = child[nr] = true;
51         }
52 
53         int root = 0;
54         for (int i = 0; i < vt.size(); i++) {
55             if (!child[vt[i]]) {
56                 root = vt[i];
57                 break;
58             }
59         }
60 
61         preorder_search(root);
62 
63         cout << endl;
64     }
65     return 0;
66 }