二叉搜索树之：【中序遍历一棵二叉搜索树】【给一棵有固定形态的二叉搜索树填值】【用BST中序遍历的性质填值】【之前讲过层序遍历】

#include 
using namespace std;
const int N=110;
int l[N],r[N],w[N];
int a[N];
//a是指原序列
//w是维护二叉搜索树每个点的权值
 
 
//用中序遍历遍历二叉搜索树
void dfs(int u,int &k)
{
   if(u==-1) return;
   dfs(l[u],k);
   w[u]=a[k++];
   dfs(r[u],k);
}
 
void bfs()
{
    queue<int> q;
    q.push(0);
    
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        
        cout<" ";
        
        if(l[t]!=-1)
        q.push(l[t]);
        
        if(r[t]!=-1)
        q.push(r[t]);
    }
 
}
 
 
int main()
{
    int n;
    cin>>n;
    
    for(int i=0;i
    {
        cin>>l[i]>>r[i];
    }
    
    for(int i=0;i
    {
        cin>>a[i];
    }
    
    sort(a,a+n);
    
    int k=0;
    
    dfs(0,k);   //按照中序遍历遍历二叉树
    
    bfs();
 
    return 0;
}