1064. Complete Binary Search Tree (30)

题目描述：

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）难点在这个数组中确定根节点。

（2）用queue进行层遍历。

参考代码：

 

#include<iostream>  
#include<algorithm>  
#include<queue>  
#include<cmath>  
using namespace std;  
  
struct TreeNode  
{  
    int value;  
    TreeNode * left;  
    TreeNode * right;  
    TreeNode(int v):value(v),left(NULL),right(NULL){}  
    TreeNode():left(NULL),right(NULL){}  
};  
  
void build(int *array,int len, TreeNode **r)  
{  
    int level = 0;  
    int i;  
    for(i=0; i<100; i++)  
    {  
        //n层满二叉树的节点个数是  pos(2.0,i);  
        if((int)pow(2.0,i) -1 > len)  
        {  
            level = i;  break;  
        }  
    }  
    int remain; //最后一层节点的个数  
    int left; //左子树的节点个数  
    int right; //右子树的节点个数  
    int last; //最后一层最左边节点的编号  
    int c;//满二叉树中节点的个数  
    c = (int)pow(2.0,level-1) - 1;  
    remain = len - c ;  
    last = c + 1;  
    // last/2 代表根节点的左子树在最后一层上可容纳的节点个数  
    if(remain > last/2){  
        left = (c-1)/2 + last/2;          
    }else{  
        left = (c-1)/2 + remain;  
    }  
    right = len - left - 1;  
      
    TreeNode *root = new TreeNode();  
    *r = root;  
    root->value = array[left];  
    if(left > 0)  
        build(array, left, &root->left);  
    if(right > 0)  
        build(array+left+1, right, &root->right);  
}  
  
int main()  
{  
    int n,i;  
    while(cin>>n)  
    {  
        int *array = new int[n];          
        for(i=0; i<n; i++)  
            cin>>array[i];  
        sort(array,array+n);  
        TreeNode *root = NULL;  
        build(array,n,&root);  
        queue<TreeNode *> que;          
        que.push(root);  
        bool flag = false;  
        TreeNode *temp;  
        while(!que.empty()){  
            if(flag)  
                cout<<" ";  
            else  
                flag = true;  
            temp = que.front();  
            if(temp){  
                cout<<temp->value;  
                if(temp->left)  
                    que.push(temp->left);  
                if(temp->right)  
                    que.push(temp->right);  
            }  
            que.pop();  
        }  
        cout<<endl;  
    }  
    return 0;  
}  

 

 

补充：软件开发 , C++ ,