posts - 183,  comments - 10,  trackbacks - 0

实现一棵多叉树

这棵树可以有任意多颗子树 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 阅读(4815) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理