Topic Description (from MOOC-Chen Yue, He Qinming-Data Structure-Summer of 2019)

The binary search tree (BST) is defined recursively as a binary tree with the following attributes:

• The left subtree of a node contains only nodes whose keys are smaller than the node keys.
• The right subtree of a node contains only nodes whose keys are greater than or equal to the node keys.
• Left and right subtrees must also be binary search trees.

A complete binary tree (CBT) is a fully filled tree, which may be filled from left to right except for the bottom.

Given a series of different non-negative integer keys, a unique BST can be constructed if the tree must also be CBT. You should output the hierarchical traversal sequence of this BST.

Input specification:
Each input file contains a test case. For each case, the first line contains a positive integer N (< 10000). Then the next line gives N different nonnegative integer keys. All numbers in a row are separated by spaces, not more than 2000.

Output Specifications:
For each test case, print the corresponding complete binary search tree hierarchical traversal sequence in one line. All numbers in a row must be separated by spaces, and no additional spaces are allowed at the end of the row.

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

Idea Solution: (Code below)

Code details:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Maxsize 1050
int NewTree[Maxsize];
int num[Maxsize];
int cmp(const void *a,const void *b)//The order from small to large
{
    return *(int *)a-*(int *)b;
}
int GetLength( int changenum )
{
	int i,value = 0,temp,current,left,root;
	for(i = 1 ;i <= changenum ;i++)
	{
       value = pow(2,i) - 1;
       if( value >= changenum ) //Find the number of floors on the last floor
		break;
	}
	if(value == changenum ) //It happens to be a complete binary tree, and the last line is full.
	{
		left = (value - 1)/2;
	}
	else//The last line is not full
	{
		temp = ( pow(2,i-1) - 2 )/2; //Number of front i-1 nodes
		current = changenum - pow(2,i-1) + 1;
		if(current <= pow(2,i-1)/2)//Not more than half of the last line
			left = temp + current;//Left subtree
		else   //More than half of the last line
			left = temp + pow(2,i-1)/2;//Left subtree
	}
	return  left;
}
void CreateTree(int left,int right,int root)
{
	int n = right - left + 1;   //Calculate total length
	if(n == 0)return ;   //Recursive jump-out condition
	int l = GetLength( n ); //Calculating Subtree Length
	NewTree[root] = num[left + l];  //Pass values to new arrays
	int leftroot = root * 2 + 1;    //Left subtree
	int rightroot = leftroot + 1;     //Right subtree
	CreateTree(left,left + l - 1,leftroot); //Left subtree recursion
	CreateTree(left + l + 1,right,rightroot);   //Right subtree recursion
}
int main()
{
	int N = 0,i = 0;
	scanf("%d",&N);
	for(i = 0; i <= N - 1;i++)
		scanf("%d",&num[i]);
	qsort(num,N,sizeof(int),cmp);  //Ranking from small to large
	CreateTree(0,N - 1,0);
	for(i = 0;i <= N - 1;i++)
		if(i <= N - 2)
			printf("%d ",NewTree[i]);
        else
			printf("%d",NewTree[i]);
	return 0;
}

Ideas and solutions:

1. The first is to understand that a complete binary tree is a fully filled tree, which may be filled from left to right in addition to the bottom.
2. Meet the rules of "small left, big right"
3. In linked lists and arrays, they tend to be arrays because they traverse the sequence in the order of ranks of the complete binary search tree, from top to bottom, from left to right.
4. At the beginning, the arrays are sorted from small to large. Why?
   Because on the left side of the root, the left subtree is less than the value of the root, while the right subtree is larger than the root, so first in small order, according to the number of nodes, calculate the value of the root at this time.
5. At this time, it is divided into two parts: left and right subtrees, so the algorithm of finding the main root can be repeated.

So how to find roots?
This can be found by using the properties of binary trees, as follows:

int GetLength( int changenum )
{
	int i,value = 0,temp,current,left,root;
	for(i = 1 ;i <= changenum ;i++)
	{
       value = pow(2,i) - 1;
       if( value >= changenum ) //Find the number of floors on the last floor
		break;
	}
	if(value == changenum ) //It happens to be a complete binary tree, and the last line is full.
	{
		left = (value - 1)/2;
	}
	else//The last line is not full
	{
		temp = ( pow(2,i-1) - 2 )/2; //Number of front i-1 nodes
		current = changenum - pow(2,i-1) + 1;
		if(current <= pow(2,i-1)/2)//Not more than half of the last line
			left = temp + current;//Left subtree
		else   //More than half of the last line
			left = temp + pow(2,i-1)/2;//Left subtree
	}
	return  left;
}