04-树6 Complete Binary Search Tree

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

题意：给出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