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:

1 2	10 1 2 3 4 5 6 7 8 9 0

Sample Output:

1	6 3 8 1 5 7 9 0 2 4

分析:

二叉搜索树：左子树 < 根结点 < 右子树；

完全二叉树：元素依次从上到下，从左到右顺序存储；

完全二叉搜索树即包含以上两者的特性。

根据元素个数构造完全二叉树结构，用数组顺序存储，将原来的数组按从小到大排序得到有序数组；根据完全二叉树结构可以定位到比根结点小的元素个数L，及比根结点大的元素个数，所以根结点的值为有序数组中的第L个，依次分段处理根结点的左部分、右部分。

主要步骤

读取数组个数及数组元素
对数组进行排序
获取完全二叉搜索树GetBinTree
打印新的数组

获取完全二叉搜索树,递归GetBinTree

判断是否到达递归的边界，即左边到达右边或右边越过左边
计算根结点左边有多长GetLeftLength
从有序数组Arr中找的第ALeft+L个元素即为Bin数组的根结点
计算当前根结点的左孩子和右孩子
递归获取以根结点为界的左部分、右部分的新的根结点

获取当前根结点的左子树的长度GetLeftLength

求出n个结点为满二叉树的树高
求出最底层树结点的个数
求最底层结点属于左子树部分的个数
求得根结点左子树部分长度

// 完全二叉搜索树 CBST(CST + BST)
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define MAXSIZE 10001
int *Arr;
int *Bin;

// 用比较排序O(N^2)复杂度，但代码简单
void SortArray(int n) {
    int i, j, temp;
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            if (Arr[i] > Arr[j]) {
                temp = Arr[i];
                Arr[i] = Arr[j];
                Arr[j] = temp;
            }
        }
    }
}

// 获取当前根结点的左子树的长度，左子树也为完全二叉树
int GetLeftLength(int n) {
    // 满二叉树高h, 最底层结点数x, 左子树长度l
    int h, x, l;
    // 1.求出n个结点为满二叉树的树高
    h = (int) log2(n + 1);
    // 2.求出最底层树结点的个数
    x = n + 1 - pow(2, h);
    // 3.求最底层结点属于左子树部分的个数
    if (pow(2, h - 1) < x) {
        x = pow(2, h - 1);
    }
    // 4.求得根结点左子树部分长度
    l = pow(2, h - 1) - 1 + x;
    return l;
}

// 获取完全二叉搜索树,递归
void GetBinTree(int ALeft, int ARight, int TRoot) {
    int n, L, LeftTRoot, RightTRoot;
    n = ARight - ALeft + 1;
    // 1.判断是否到达递归的边界，即左边到达右边或右边越过左边
    if (n == 0)
        return;
    // 2.计算根结点左边有多长
    L = GetLeftLength(n);
    // 3.从有序数组Arr中找的第ALeft+L个元素即为Bin数组的根结点
    Bin[TRoot] = Arr[ALeft + L];
    // 4.计算当前根结点的左孩子和右孩子
    LeftTRoot = TRoot * 2 + 1;
    RightTRoot = LeftTRoot + 1;
    // 5.递归获取以根结点为界的左部分、右部分的新的根结点
    GetBinTree(ALeft, ALeft + L - 1, LeftTRoot);
    GetBinTree(ALeft + L + 1, ARight, RightTRoot);
}

// 打印数组
void PrintArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        if (i == n - 1)
            printf("%d", arr[i]);
        else
            printf("%d ", arr[i]);
    }
}

int main() {
    int i, n;
    scanf("%d", &n);
    Arr = (int *) malloc(sizeof(int) * n);
    Bin = (int *) malloc(sizeof(int) * n);
    // 1.读取数组个数及数组元素
    for (i = 0; i < n; i++) {
        scanf("%d", &Arr[i]);
    }
    // 2.对数组进行排序
    SortArray(n);
    // 3.获取完全二叉搜索树
    GetBinTree(0, n - 1, 0);
    // 4.打印新的数组
    PrintArray(Bin, n);
    return 0;
}

小结：

熟悉二叉搜索树、完全二叉树结构特性；
从特殊个例到全体通用，构造递归函数。