04-树6 Complete Binary Search Tree (30 分)

这道题除了陈越姥姥上课讲的思路之外，还有另一种思路：完全二叉搜索树的中序遍历是顺序序列，已知当前的顺序序列，可以倒推出原来的完全二叉搜索树。

下面的代码填写的是姥姥讲的思路，通过公式计算他们的左儿子、右儿子的个数。

input数组为已经排好序的完全二叉树，output为未排序待输出数组，如下图所示：

 #include <iostream>
 #include <algorithm>
 #include <cmath>
 using namespace std;
 const int maxn = 1001;
 int input[maxn], output[maxn];
 int getLeftLength(int n) {
 	double h = log(n + 1) / log(2.0);
 	int H = (int)h;
 	int x = floor(n + 1 - pow(2.0, H));
 	int x_2 = floor(pow(2.0, H - 1));
 	x = min(x, x_2);
 	return (int)(pow(2.0, H - 1) + x-1);
 }
 
 
 
 
 void solve(int left, int right, int root) {
 	//初始调用为solve(0,n-1,0)
 	int n = right - left + 1;
 	if (n == 0)return;
 	int L = getLeftLength(n);
 	output[root] = input[L + left];
 	int leftoutputRoot = root * 2 + 1;//左儿子结点在数组的下标
 	int rightoutputRoot = root * 2 + 2;
 	solve(left, L + left-1, leftoutputRoot);//递归解决左儿子
 	solve(L + left + 1, right, rightoutputRoot);//递归解决右儿子
 
 }
 
 
 
 
 int main() {
 	int n;
 	cin >> n;
 	for (int i = 0; i < n; i++) {
 		cin >> input[i];
 	}
 	sort(input, input + n);
 	//cout<<getLeftLength(n);
 	solve(0, n - 1, 0);
 	cout << output[0];
 	for (int i = 1; i < n; i++) {
 		cout << " " << output[i];
 	}
 	system("pause");
 	return 0;
 }