PAT(甲级)渡劫(十)-Build A Binary Search(30)

PAT(甲级)渡劫(十)-Build A Binary Search(30)

算法思想：

首先在输入数据的时候就构造二叉树的结构，然后将输入的数据进行排序，将排序好的数字在中序遍历中赋值给构造好的二叉树，最后用层次遍历输出即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define N 200
using namespace std;

struct TNode{
    int data;
    struct TNode *lchild,*rchild;
}Tree[N];
int key[N];
int cnt = 0;
void inOrder(TNode *T){
    if(T != NULL){
        inOrder(T->lchild);
        T->data = key[cnt++];
        inOrder(T->rchild);
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i <n ; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a != -1){
            Tree[i].lchild = &Tree[a];
        }else{
            Tree[i].lchild = NULL;
        }

        if(b != -1){
            Tree[i].rchild = &Tree[b];
        }else{
            Tree[i].rchild = NULL;
        }
    }
    for(int i = 0 ; i < n ; i++)
        scanf("%d",&key[i]);
    sort(key,key+n);

    inOrder(&Tree[0]);

    queue<TNode> Q;
    Q.push(Tree[0]);
    printf("%d",Tree[0].data);
    while(Q.empty() != true){
        TNode tmp = Q.front();
        Q.pop();
        
        if(tmp.lchild != NULL){
            printf(" %d",tmp.lchild->data);
            Q.push(*(tmp.lchild));
        }
        if(tmp.rchild != NULL){
            printf(" %d",tmp.rchild->data);
            Q.push(*(tmp.rchild));
        }
    }
    return 0;
}

运行结果：