PAT

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

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

代码：

#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; }