單詞積累

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
結(jié)尾無空行

Sample Output:

6 3 8 1 5 7 9 0 2 4
結(jié)尾無空行

思路

利用完全二叉排序樹的性質(zhì)，找到根節(jié)點 左節(jié)點 右節(jié)點汇恤，來完成建樹

建樹完成后，利用層次遍歷即可得到最終結(jié)果

看了別人的題解之后惨寿，感覺自己處理地麻煩太多了槐秧。更優(yōu)的思路是利用排序贤壁，得到二叉樹的中序序列（二叉排序樹的性質(zhì)：中序遍歷結(jié)果就是數(shù)字的升序序列）疏遏，然后再通過中序序列建樹提揍，樹的存儲序列即為層次序列的值（完全二叉樹的性質(zhì)：從1開始編號的完全二叉樹溉旋，i節(jié)點的左孩子編號為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;  // 處理的節(jié)點數(shù) 
    int height = floor(log(all + 1) / log(2));  // 滿層的高度 
    int now = pow(2, height) - 1;  // 滿層的節(jié)點數(shù) 
    int left = (now - 1) / 2;
    int right = left;
    left += a;
    int next = pow(2, height);  //下一層的節(jié)點數(shù) 
    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<<" ";
    }
}