PAT 甲级 刷题日记|A 1064 Complete Bina

单词积累

complete 完整的 完全的

exception 例外 异议

题目

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input:

10
1 2 3 4 5 6 7 8 9 0
结尾无空行

Sample Output:

6 3 8 1 5 7 9 0 2 4
结尾无空行

思路

利用完全二叉排序树的性质，找到根节点 左节点 右节点，来完成建树

建树完成后，利用层次遍历即可得到最终结果

看了别人的题解之后，感觉自己处理地麻烦太多了。更优的思路是利用排序，得到二叉树的中序序列（二叉排序树的性质：中序遍历结果就是数字的升序序列），然后再通过中序序列建树，树的存储序列即为层次序列的值（完全二叉树的性质：从1开始编号的完全二叉树，i节点的左孩子编号为2i，右孩子编号为2i+1），非常巧妙

代码1

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000 + 2;
int num[maxn];
vector<int> res;

struct node{
    int data;
    node* leftchild;
    node* rightchild;
    node(int d): data(d), leftchild(NULL), rightchild(NULL){
    } 
};

node* create(int a, int b) {
    if (a == b) {
        node* anode = new node(num[a]);
        return anode;
    }
    if (a > b) return NULL; 
    int all = b - a + 1;  // 处理的节点数 
    int height = floor(log(all + 1) / log(2));  // 满层的高度 
    int now = pow(2, height) - 1;  // 满层的节点数 
    int left = (now - 1) / 2;
    int right = left;
    left += a;
    int next = pow(2, height);  //下一层的节点数 
    if ((all - now) <= next / 2) left += (all - now);
    else {
        left += next / 2;
        right += all - now - next/2;
    }
    node* root = new node(num[left]);
    root->leftchild = create(a, left - 1);
    root->rightchild = create(left + 1, b);
    return root;
}

void level(node* root) {
    queue<node*> mq;
    mq.push(root);
    while(!mq.empty()) {
        node* now = mq.front();
        mq.pop();
        res.push_back(now->data);
        if(now->leftchild != NULL) mq.push(now->leftchild);
        if(now->rightchild != NULL) mq.push(now->rightchild);
    }
    return;
}

int main() {
    int len;
    cin>>len;
    for (int i = 0; i< len; i++) {
        cin>>num[i];
    }
    sort(num, num+len);
    node* root = create(0,len-1);
    level(root);
    for (int i = 0; i < len; i++) {
        cout<<res[i];
        if (i != len - 1) cout<<" ";
    }
} 

代码2

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10000;
int len;
int index = 0;
int num[maxn];
int res[maxn];

void Inorder(int root) {
    if (root > len) return;
    Inorder(root * 2);
    res[root] = num[index++];
    Inorder(root * 2 + 1);  
}

int main() {
    cin>>len;
    for (int i = 0; i < len; i++) {
        cin>>num[i];
    }
    sort(num, num + len);
    Inorder(1);
    for (int i = 1; i <= len; i++) {
        cout<<res[i];
        if (i != len) cout<<" ";
    }
}