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
代码语言：javascript复制题意：给出n个节点，我们需要把它放在完全二叉树里面，并且保持二叉搜索树的性质，之后层次遍历输出这颗完全二叉搜索树的所有节点
思路：我们把给定的节点排好序放在一个数组里，因为我们要把这些书放在一颗完全二叉树里面，所以给我们n的节点，我们肯定可以求出左子树有多少个，这样就知道这个二叉树的根了，及数组里面前n个是左子树，n 1是根节点，因为它要满足搜索二叉树的性质，即左子树的节点小于跟节点，之后便是递归求根节点的下面的左子树的根节点和右子树的根节点，递归就可以完成，这一题花了我大约两个多小时，主要还是递归那个函数不会写，收获很多，这题我肯定要写个总结了
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int tree[1001];
int value[1001];
int k=0;//k为tree的数组下标
//思路理一遍，我们先把读入的数据排好放在一个数组里，接着递归去找根节点。。。
int seekroot(int n) { //给二叉树的n个节点，返回其最大左子树的个数
int i;
for ( i = 1; n >=pow(2, i) - 1; i ) {
}
if((n-(pow(2,i-1)-1))<=pow(2,i-2))
return (pow(2, i - 1) - 1) / 2 (n - pow(2, i - 1) 1);
else
return (pow(2, i - 1) - 1) / 2 pow(2, i - 2);
}
void solve(int left ,int right ,int root) {
int leftroot, rightroot;
int n = right - left 1;
if (n == 0) return;
int l = seekroot(n);//偏移量
tree[root] = value[left l];
leftroot = root * 2 1;
rightroot = leftroot 1;
solve(left, left l - 1, leftroot);
solve(left l 1, right, rightroot);
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i )
cin >> value[i];
sort(value, value n);
solve(0, n - 1, 0);
//太特么坑的我头破血流。。这个n变了，最后变成了0，找了老半天的bug,因为n我设为了全局变量
bool flag=0;
for (int i = 0; i < n; i ) {
if(flag)
cout<<" ";
cout << tree[i] ;
flag=1;
}
}废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：04-树6 Complete Binary Search Tree
