给定树的结构,采用中序遍历填进去就可以了
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 110;
struct node {
int data;
int lchild, rchild;
}Node[maxn];
int n, num[maxn], cnt;
vector<int>layer;
void inorder(int index)
{
if (index>n)return;
if (Node[index].lchild!=-1)inorder(Node[index].lchild);
Node[index].data = num[cnt++];
if (Node[index].rchild!=-1)inorder(Node[index].rchild);
}
void layerorder(int root)
{
queue<int>q;
q.push(root);
while (!q.empty())
{
int top = q.front();
q.pop();
layer.push_back(Node[top].data);
if (Node[top].lchild != -1)q.push(Node[top].lchild);
if (Node[top].rchild != -1)q.push(Node[top].rchild);
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d%d", &Node[i].lchild, &Node[i].rchild);
}
for (int i = 0; i < n; i++)scanf("%d", &num[i]);
sort(num, num + n);
inorder(0);
layerorder(0);
for (int i = 0; i < n; i++)
{
printf("%d", layer[i]);
if (i != n - 1)printf(" ");
}
return 0;
}
inorder也可以写成这样
void inorder(int index)
{
if (index == -1)return;
inorder(Node[index].lchild);
Node[index].data = num[cnt++];
inorder(Node[index].rchild);
}