PAT_A_1099 Build A Binary Search Tree

题意：建立一颗二叉搜索树，当建立好后，把给定的一些值填入节点中，最后求层序遍历

思路：先建立该二叉树，然后进行中序遍历，可以看到二叉搜索树的中序遍历即是数字从小到大的映射，故中序遍历的时候把该点的值填入其中，然后也可以填入层次以及下标，根据层次和下标进行排序，就可以得到层次遍历了

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n = 0,num = 0;
struct node {
	int data,l,r,index,level;
}nodes[150];
vector<int> p;
void inTravel(int root,int index,int level){
	if (nodes[root].l != -1)inTravel(nodes[root].l, index * 2, level + 1);
	nodes[root].data = p[num++];
	nodes[root].index = index;
	nodes[root].level = level;
	if (nodes[root].r != -1)inTravel(nodes[root].r, index * 2+1, level + 1);
}
bool com(node a,node b) {
	if (a.level != b.level)return a.level < b.level;
	else return a.index < b.index;
}
int main(){
	cin >> n;
	p.resize(n);
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		nodes[i].l = l;
		nodes[i].r = r;
	}
	for (int i = 0; i < n; i++) scanf("%d",&p[i]);
	sort(p.begin(),p.end());
	inTravel(0,0,0);
	sort(nodes + 0, nodes + n,com);
	for (int i = 0; i < n; i++) {
		printf("%d%s",nodes[i].data,i==n-1?"\n":" ");
	}
	system("pause");
	return 0;
}