首页 > > 程序设计 > C/C++ >

PAT A1099

2018-06-17 22:11:27来源：未知阅读 ()

https://www.patest.cn/contests/pat-a-practise/1099

题意大概：

给定一棵BST的节点数，树的结构，以及各个节点的权值，求此树层次遍历的结果

解题思路：

1.使用孩子兄弟法存储输入数据

2.对各个节点的权值进行排序

3.通过中序遍历可以得到各节点从小到大的的有序权值。这里通过中序遍历对结构体重的权值进行赋值（构建BST）

4.通过层次遍历获取结果

5.根据题目要求，格式化输出结果。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 using namespace std;
 5 const int mmax=101;
 6 struct node{
 7     int l,r;
 8     int data;
 9 }tree[mmax];
10 
11 int num;
12 void midtrv(int root,int val[])
13 {
14     if(root!=-1)
15     {
16         midtrv(tree[root].l,val);
17         tree[root].data=val[num];
18         num++;
19         midtrv(tree[root].r,val);
20     }    
21 }
22 
23 queue<int> myqueue;
24 int val[mmax];
25 void leveltrv(int root)
26 {
27     num=0;
28     if(root!=-1)
29     {
30         myqueue.push(root);
31         while(!myqueue.empty())
32         {
33             int t=myqueue.front();
34             myqueue.pop();
35             val[num++]=tree[t].data;
36             if(tree[t].l!=-1)
37                 myqueue.push(tree[t].l);
38             if(tree[t].r!=-1)
39                 myqueue.push(tree[t].r);
40         }
41     }
42 }
43 int main()
44 {
45 
46     int n;
47 
48     num=0;
49     cin>>n;
50     
51     for(int i=0;i<n;i++)
52     {
53         cin>>tree[i].l>>tree[i].r;
54     }
55     for(int i=0;i<n;i++)
56     cin>>val[i];
57     
58     sort(val,val+n);
59     midtrv(0,val);
60     leveltrv(0);
61     
62     for(int i=0;i<n-1;i++)
63     cout<<val[i]<<" ";
64     cout<<val[n-1]<<endl;
65     return 0;
66 }