pat 1064

此题的思路

  1. 如果用数组来存放完全二叉树,那么对完全二叉树中的任何一个节点(编号为x,其根节点编号为1), 其左孩子的编号一定是2x , 右孩子一定是2x+1,由此可以开一个CBI[MAX]数组存放二叉树
  2. 考虑到对于一颗二叉排序树来说,其中中序遍历必然是递增有序的,此时,先将输入的数据按照从大到小 的序号排序,然后通过中序遍历为CBI[MAX]赋值,如此便可以得出一个完全二叉排序树
  3. 对于树的静态表示方法,讲数组的数据按序输出即为层序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
#define MAX 1010
using namespace std;
int number[MAX]= {0} , N;
int CBI[MAX] , index = 0;
void inOrder(int root)
{
if(root > N)
return;
inOrder(root*2);
CBI[root] = number[index++];
inOrder(root * 2 +1);
}
int main()
{
cin>>N;
int i;
for(i = 0 ; i < N ; ++i)
{
cin>>number[i];
}
sort(number , number+N);
inOrder(1);//在树的静态表示方法中,数组0处的单元一般不使用,根节点必须为1
bool flag = true;
for(i = 1 ; i <= N ; ++i)
{
if(flag)
{
cout<<CBI[i];
flag = false;
}
else
cout<<" "<<CBI[i];
}
return 0;
}

热评文章