完全二叉搜索树

• 完全二叉搜索树可以使用一个一维数组来存储

• 完全二叉树指除了最后一层，其他层的所有元素填满。最后一层可以不用填满，但要靠左填。如果最后一层也完全填满称为完美二叉树或者满二叉树。

• 

通过 0~9 构造出来的完全二叉树是这样的。其层序遍历为 6 3 8 1 5 7 9 0 2 4 。可以看到 n 的左子树是 n * 2 ， n 的右子树是 n * 2 + 1 。因此说完全二叉搜索树可以通过一个一维数组来进行存储。而如果需要输出其层序遍历的结果只需要 for (int i = 1; i <= n; i ++ ) 输出一遍即可。

#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

const int N = 1010;
int w[N], tr[N];
int k;
int n;

void dfs(int u)
{
    if (u * 2 <= n) dfs(u * 2);
    tr[u] = w[k ++ ];
    if (u * 2 + 1 <= n) dfs(u * 2 + 1);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> w[i];

    sort(w, w + n);

    dfs(1);

    printf("%d", tr[1]);
    for (int i = 2; i <= n; i ++ ) printf(" %d", tr[i]);

    return 0;
}