完全二叉查找树

1064 Complete Binary Search Tree (30 分)

给定一组key值，建立完全二叉查找树。

• 已知中序遍历序列（BST的中序遍历序列有顺序性）
• 该二叉树是完全二叉树。下标为n的结点，左孩子下标为2n+1，右孩子下标2n+2。（下标从0开始）

• 思路：在中序遍历时给结点赋值。

#include <cstdio>
#include <algorithm>

using namespace std;
int nn, keys[2001], bst[2001], _index = 0;

void in_sort(int root_index) {
    if (2 * root_index + 1 < nn) in_sort(2 * root_index + 1);
    bst[root_index] = keys[_index++];
    if (2 * root_index + 2 < nn) in_sort(2 * root_index + 2);
}

int main() {
    scanf("%d", &nn);
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &keys[i]);
    }
    sort(keys, keys + nn);
    in_sort(0);
    printf("%d", bst[0]);
    for (int i = 1; i < nn; ++i) {
        printf(" %d", bst[i]);
    }
    return 0;
}