二叉搜索树的性质:中序遍历是有序的
于是,将原数组排序,然后以中序的顺序放置到树中
层序遍历输出结果即可
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
typedef struct Node{
int val;
int left; //左右表示编号
int right;
}; //这里有分号才表示结构体定义完毕
Node tree[N];
int arr[N];
int n;
int cnt;
void dfs(int u) //u
{
if(u==-1) return;
dfs(tree[u].left);
tree[u].val=arr[cnt++];
dfs(tree[u].right);
}
void bfs()
{
queue<Node> q;
q.push(tree[0]);
while(q.size())
{
auto t=q.front(); //q.front访问队首
q.pop();
cout<<t.val<<' ';
if(t.left!=-1) q.push(tree[t.left]);
if(t.right!=-1) q.push(tree[t.right]);
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
tree[i].left=l; //输入是按照编号0 1 2 3...顺序来的,尽管层序并不是这个顺序
tree[i].right=r;
}
for(int i=0;i<n;i++) cin>>arr[i];
sort(arr,arr+n);
dfs(0);
bfs();
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
struct Node{
int val;
int left;
int right;
};
int n;
Node tree[N];
int arr[N];
int cnt;
void dfs(int u)
{
if(u==-1) return;
dfs(tree[u].left);
tree[u].val=arr[cnt++];
dfs(tree[u].right);
}
void bfs() //层序遍历就是bfs
{
queue<Node> q;
q.push(tree[0]);
while(q.size())
{
Node t=q.front();
q.pop();
cout<<t.val<<' ';
if(t.left!=-1) q.push(tree[t.left]);
if(t.right!=-1) q.push(tree[t.right]);
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
tree[i].left=x;
tree[i].right=y;
}
for(int i=0;i<n;i++) cin>>arr[i];
sort(arr,arr+n);
dfs(0);
bfs();
return 0;
}