C语言建立完全二叉搜索树

Question

建立完全二叉搜索树

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.

我的代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int T[1050];
int List[1050];

void Bubble(int* List,int Length)
{/*冒泡排序*/
    int i,j,temp;
    for( i=0; i<Length-1; i++ ){
        for( j=0; j<Length-1-i; j++ ){
            if(List[j]>List[j+1]){
                temp = List[j];
                List[j] = List[j+1];
                List[j+1] = temp;
            }
        }
    }    
}

int GetLeftLength(int Length)
{
    int LeftLength;
    if(Length==1) LeftLength=0;
    else if(Length<=3) LeftLength=1;
    else{
        int row;
        for( row=1; pow(2,row)-1<Length ; row++ );
        if(pow(row,2)-1==Length) LeftLength = Length/2;
        else{
            int LastRow = pow(2,row-2);/*上一行*/
            int X = Length - pow(2,row-1)+1;/*该行*/
            int LastSum = pow(2,row);
            if(X>=LastRow){
                LeftLength = LastRow*2-1;
            }else{
                LeftLength = LastRow+X-1;
            }
        }
    }
    return LeftLength;
}

void solve( int ListLeft, int ListRight, int TRoot )
{    /*递归为T[]赋值*/
    int Length = ListRight - ListLeft + 1;
    
    if(Length==0) return;
    
    int LeftLength = GetLeftLength(Length);//子树也是完全二叉树 
    
    T[TRoot] = List[ListLeft + LeftLength];
    int LeftRoot = TRoot*2;
    int RightRoot = LeftRoot + 1;
    
    solve(ListLeft,ListLeft+LeftLength-1,LeftRoot);
    /*如果没有左子树，ListLeft+LeftLength-1比ListLeft少1*/
    solve(ListLeft+LeftLength+1,ListRight,RightRoot);
    /*
    如果没有右子树，但有左子树，ListLeft+1为树根，
    加上LeftLength后比ListRight多1 
    */
}



int main()
{
    int N,i;
    scanf("%d",&N);
    for(i=0;i<N;i++)
        scanf("%d",&(List[i]));
    Bubble(List,N);
    solve(0,N-1,1);
    for(i=1;i<N;i++)
        printf("%d ",T[i]);
    printf("%d",T[i]);
    return 0;
}

结果

其实我不是用这个方法写的，我最初的方法也就50行代码，这个方法是课上给的方法，本来想练练他这方法，哪知道做不出来了，好不容易到现在，还有一处错误，可惜我也看不懂哪错了。他这个方法其实就找根结点赋值，然后将数组分成左右子树，再向下递归，一直做到Length=0就停了

补充一下，我这边用的数组存树，是从1开始的。不是0。其他有什么问题可以直接问，毕竟不写注释是我的问题。

Answer 1

GetLeftLength那里计算的不对，修改后

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
int T[1050];
int List[1050];
 int Min( int X,int Y)
{
    return (X<Y?X:Y);
}
void Bubble(int* List,int Length)
{/*冒泡排序*/
    int i,j,temp;
    for( i=0; i<Length; i++ ){
        for( j=0; j<Length-1; j++ ){
            if(List[j]>List[j+1]){
                temp = List[j];
                List[j] = List[j+1];
                List[j+1] = temp;
            }
        }
    }    
}
 
int GetLeftLength(int n)
{
    int K = (int)(log(n+1)/log(2));//完美二叉树的层数

    int X = n+1-(int)pow(2,K);     //根据完美二叉树的层数 求出 最下面一层非完美的叶结点个数
    
    X = Min( X,(int)pow(2,K-1));
    
    int L = (int)pow(2,K-1) - 1 + X; //根结点左边结点个数
    
    return L;

}
 
void solve( int ListLeft, int ListRight, int TRoot )
{    /*递归为T[]赋值*/
    int Length = ListRight - ListLeft + 1;
    
    if(Length==0) return;
    
    int LeftLength = GetLeftLength(Length);//子树也是完全二叉树 
    
    T[TRoot] = List[ListLeft + LeftLength];
    int LeftRoot = TRoot*2;
    int RightRoot = LeftRoot + 1;
    
    solve(ListLeft,ListLeft+LeftLength-1,LeftRoot);
    /*如果没有左子树，ListLeft+LeftLength-1比ListLeft少1*/
    solve(ListLeft+LeftLength+1,ListRight,RightRoot);
    /*
    如果没有右子树，但有左子树，ListLeft+1为树根，
    加上LeftLength后比ListRight多1 
    */
}
 
 
 
int main()
{
    int N,i;
    scanf("%d",&N);
    for(i=0;i<N;i++)
        scanf("%d",&(List[i]));
    Bubble(List,N);
    solve(0,N-1,1);
    for(i=1;i<N;i++)
        printf("%d ",T[i]);
    printf("%d",T[i]);
    return 0;
}