PAT甲级-1064 Complete Binary Search Tree

题目

题目大意

给出n个节点，可以确定唯一的完全二叉排序树，要求输出该树的层序遍历。

思路

这道题要考虑完全二叉树和二叉排序树的性质，将两者结合起来能够很迅速的解决题目。二叉排序树一个很重要的特点就是中序遍历是从小到大的排序。那么题目中给出的序列经过排序就是二叉排序树的中序遍历，相当于知道了排序树的中序遍历，求其层序遍历。完全二叉树的特点是左节点孩子下标是2 * root + 1，右孩子下标是2 * root + 2，层序遍历下标正好是从小到大的顺序。知道一棵树是完全二叉树，且总节点数确定，那么这棵树的形状就唯一确定了，只需要往里面填充数字即可。怎么填充，可以对这棵树进行中序遍历（相当于节点的id），将其与排序树的中序遍历（相当于节点的值）对应，就知道哪个萝卜哪个坑了。

知识点

/*if (it != mp.end() - 1){

            cout << " ";

        }*/  // 不能写if (it != mp.end() - 1)，end()返回的是一个指向末尾之后位置的迭代器（超出实际元素范围），不能直接用于减法操作

可以建一个迭代器指向容器中的最后一个元素， auto last = prev(mp.end());再用it != last作区分。

代码

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int n;
vector<int> mid;

void getMid(int root){
    if (root >= n){
        return;
    }
    getMid(2 * root + 1);
    mid.push_back(root);
    getMid(2 * root + 2);
}  // 求完全二叉树的中序遍历(id)

int main(){
    cin >> n;
    getMid(0);
    vector<int> v(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());  // 二叉排序树的中序遍历(data)
    for (int i = 0; i < n; i++){
        mp[mid[i]] = v[i];
    }  // 建立从id到data的映射

    auto last = prev(mp.end());
    for (auto it = mp.begin(); it != mp.end(); it++){  // mp自动按层序遍历顺序排序
        cout << it->second;
        if (it != last){
            cout << " ";
        }
        /*if (it != mp.end() - 1){
            cout << " ";
        }*/  // 不能写if (it != mp.end() - 1)，end()返回的是一个指向末尾之后位置的迭代器（超出实际元素范围），不能直接用于减法操作
    }
    cout << endl;

    return 0;
}