實現一棵多叉樹
這棵樹可以有任意多顆子樹 0-n
1
2 3 4
5 6 7 8
輸入建立二叉樹，輸入的格式是每個節點的具體數據和擁有的孩子數目
例如上面的樹是這樣建成的：
1 3
2 2
5 0
6 0
3 1
7 0
4 1
8 0
1 #include <iostream>
2 #include <vector>
3 #include <queue>
4 using namespace std;
5
6 struct node
7 {
8 int item;
9 vector<node*> children;
10 };
11
12 node* build()
13 {
14 int t, n;
15 cin >> t >> n;
16 node* p = 0;
17 p = new node;
18 p->item = t;
19 for (int i = 0; i != n; ++i)
20 {
21 p->children.push_back(build());
22 }
23 return p;
24 }
25
26 void level(node* root)
27 {
28 if (root != 0)
29 {
30 node* t;
31 queue<node*> q;
32 q.push(root);
33 while (!q.empty())
34 {
35 t = q.front();
36 cout << t->item << ' ';
37 q.pop();
38 for (vector<node*>::size_type i = 0; i != t->children.size(); ++i)
39 {
40 q.push(t->children[i]);
41 }
42 }
43 }
44 }
45
46 int main()
47 {
48 node* root = 0;
49 root = build();
50 level(root);
51 return 0;
52 }
posted on 2011-07-26 16:34
unixfy 閱讀(4958)
評論(0) 編輯 收藏 引用