数据结构week4

Week4树（中）

4.1 二叉搜索树

什么是二叉搜索树

查找问题:

• 静态查找与动态查找
• 针对动态查找，数据如何组织？

二叉搜索树（BST， Binary Search Tree），也称二叉排序树或二叉查找树

二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

1. 非空左子树的所有键值小于其根结点的键值。
2. 非空右子树的所有键值大于其根结点的键值。
3. 左、右子树都是二叉搜索树。

二叉搜索树操作的特别函数

Position Find(ElementType X, BinTree BST)//从二叉搜索树BST中查找元素X，返回其所在结点的地址；
Position FindMin(BinTree BST)//从二叉搜索树BST中查找并返回最小元素所在结点的地址；
Position FindMax(BinTree BST)//从二叉搜索树BST中查找并返回最大元素所在结点的地址。
BinTree Insert(ElementType X, BinTree BST)
BinTree Delete(ElementType X, BinTree BST)

二叉搜索树的查找操作： Find

• 查找从根结点开始，如果树为空，返回NULL

• 若搜索树非空，则根结点关键字和X进行比较， 并进行不同处理：

  1.若X小于根结点键值，只需在左子树中继续搜索；

  2.如果X大于根结点的键值， 在右子树中进行继续搜索；

  3.若两者比较结果是相等，搜索完成，返回指向此结点的指针。

Position Find(ElementType X, BinTree BST) {
    if (!BST) return NULL;          /*查找失败*/
    if (X > BST->Data) 
        return Find(X, BST->Right);	/*在右子树中继续查找*/
    else if (X < BST->Data) 
        return Find(X, BST->Left); 	/*在左子树中继续查找*/
    else                           	/* X == BST->Data */
        return BST; /*查找成功， 返回结点的找到结点的地址*/
}

由于非递归函数的执行效率高，可将“尾递归” 函数改为迭代函数

Position IterFind(ElementType X, BinTree BST){
	while (BST) {
		if (X > BST->Data)
			BST = BST->Right; 	/*向右子树中移动， 继续查找*/
		else if (X < BST->Data)
			BST = BST->Left; 	/*向左子树中移动， 继续查找*/
		else 					/* X == BST->Data */
			return BST; 		/*查找成功， 返回结点的找到结点的地址*/
	}
	return NULL; /*查找失败*/
}

查找的效率决定于树的高度

• 最大元素一定是在树的最右分枝的端结点上
• 最小元素一定是在树的最左分枝的端结点上

查找最小元素的递归函数

Position FindMin(BinTree BST){
	if (!BST) return NULL; 	/*空的二叉搜索树，返回NULL*/
	else if (!BST->Left)
		return BST; 		/*找到最左叶结点并返回*/
	else
		return FindMin(BST->Left); /*沿左分支继续查找*/
}

查找最大元素的迭代函数

Position FindMax(BinTree BST){
	if (BST)
		while (BST->Right) BST = BST->Right;
	/*沿右分支继续查找，直到最右叶结点*/
	return BST;
}

二叉搜索树的插入

分析 关键是要找到元素应该插入的位置，可以采用与Find类似的方法

BinTree Insert(ElementType X, BinTree BST){
	if (!BST) {
		/*若原树为空， 生成并返回一个结点的二叉搜索树*/
		BST = malloc(sizeof(struct TreeNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	}
	else /*开始找要插入元素的位置*/
		if (X < BST->Data)
			BST->Left = Insert(X, BST->Left);/*递归插入左子树*/
		else if (X > BST->Data)
			BST->Right = Insert(X, BST->Right);/*递归插入右子树*/
	/* else X已经存在， 什么都不做 */
	return BST;
}

二叉搜索树的删除

考虑三种情况：

1.要删除的是叶结点： 直接删除， 并再修改其父结点指针—置为NULL

2.要删除的结点只有一个孩子结点:将其父结点的指针指向要删除结点的孩子结点

3.要删除的结点有左、右两棵子树：用另一结点替代被删除结点： 右子树的最小元素 或者 左子树的最大元素

BinTree Delete(ElementType X, BinTree BST){
	Position Tmp;
	if (!BST) printf("要删除的元素未找到");
	else if (X < BST->Data)
		BST->Left = Delete(X, BST->Left); /* 左子树递归删除 */
	else if (X > BST->Data)
		BST->Right = Delete(X, BST->Right); /* 右子树递归删除 */
	else /*找到要删除的结点 */
		if (BST->Left && BST->Right) { /*被删除结点有左右两个子结点 */
			Tmp = FindMin(BST->Right);
			/*在右子树中找最小的元素填充删除结点*/
			BST->Data = Tmp->Data;
			BST->Right = Delete(BST->Data, BST->Right);
			/*在删除结点的右子树中删除最小元素*/
		}
		else { /*被删除结点有一个或无子结点*/
			Tmp = BST;
			if (!BST->Left) /* 有右孩子或无子结点*/
				BST = BST->Right;
			else if (!BST->Right) /*有左孩子或无子结点*/
				BST = BST->Left;
			free(Tmp);
		}
	return BST;
}

4.2平衡二叉树

什么是平衡二叉树

搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASL

“平衡因子（ Balance Factor，简称BF） : $BF(T) = h_L-h_R$，其中$h_L$和$h_R$分别为T的左、右子树的高度。

平衡二叉树（ Balanced Binary Tree）（ AVL树）
空树，或者任一结点左、右子树高度差的绝对值不超过1，即$|BF(T) |≤ 1$

平衡二叉树的高度能达到log2n吗？

设 $n_h$ 高度为h的平衡二叉树的最少结点数。结点数最少时：$n_h = n_{h-1} + n_{h-2} + 1$

斐波那契序列:$F_0= 1, F_1 = 1, F_i = F_{i-1} + F_{i-2}\qquad for\ i > 1 $​​

h	$n_h$	$F_h$
0	1	1
1	2	1
2	4	2
3	7	3
4	12	5
5	30	8
6	33	13
7	54	21
8	88	34
9	$\cdots$	$\cdots$

$$
n_h = F_{h+2}-1(h\geq0)
$$

$$
F_i\approx \frac{1}{\sqrt{5} }(\frac{1+\sqrt{5}}{2})^i
$$

$$
n_h\approx \frac{1}{\sqrt{5} }(\frac{1+\sqrt{5}}{2})^{h+2}-1
$$

$$
h=O(log_2n)
$$

给定结点数为$n$的$AVL$树的最大高度为$O(log2n)！$

平衡二叉树的调整

麻烦结点在发现者右子树的右边，因而叫 RR 插入，需要RR 旋转（右单旋）

麻烦结点在发现者左子树的左边，因而叫 LL 插入，需要LL 旋转（左单旋）

麻烦结点在左子树的右边，因而叫 LR 插入，需要LR 旋转

注意：有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子。

代码模板

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree; /* 二叉树类型 */
struct TNode {            /* 树结点定义 */
    ElementType Data;     /* 结点数据 */
    BinTree Left;         /* 指向左子树 */
    BinTree Right;        /* 指向右子树 */
};

BinTree Insert(BinTree BST, ElementType X) {
    if (!BST) { /* 若原树为空，生成并返回一个结点的二叉搜索树 */
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else { /* 开始找要插入元素的位置 */
        if (X < BST->Data)
            BST->Left = Insert(BST->Left, X); /*递归插入左子树*/
        else if (X > BST->Data)
            BST->Right = Insert(BST->Right, X); /*递归插入右子树*/
        /* else X已经存在，什么都不做 */
    }
    return BST;
}

BinTree Delete(BinTree BST, ElementType X) {
    Position Tmp;

    if (!BST)
        printf("要删除的元素未找到");
    else {
        if (X < BST->Data)
            BST->Left = Delete(BST->Left, X); /* 从左子树递归删除 */
        else if (X > BST->Data)
            BST->Right = Delete(BST->Right, X); /* 从右子树递归删除 */
        else { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */
            if (BST->Left && BST->Right) {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin(BST->Right);
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete(BST->Right, BST->Data);
            } else { /* 被删除结点有一个或无子结点 */
                Tmp = BST;
                if (!BST->Left) /* 只有右孩子或无子结点 */
                    BST = BST->Right;
                else /* 只有左孩子 */
                    BST = BST->Left;
                free(Tmp);
            }
        }
    }
    return BST;
}

typedef struct AVLNode *Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode {
    ElementType Data; /* 结点数据 */
    AVLTree Left;     /* 指向左子树 */
    AVLTree Right;    /* 指向右子树 */
    int Height;       /* 树高 */
};

int Max(int a, int b) {
    return a > b ? a : b;
}

int GetHeight(Position P) {
    if (P == NULL)
        return -1;
    else
        return P->Height;
}

AVLTree SingleLeftRotation(AVLTree A) { 
    /* 注意：A必须有一个左子结点B */
    /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */

    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Left), A->Height) + 1;

    return B;
}

AVLTree DoubleLeftRightRotation(AVLTree A) { 
    /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
    /* 将A、B与C做两次单旋，返回新的根结点C */

    /* 将B与C做右单旋，C被返回 */
    A->Left = SingleRightRotation(A->Left);
    /* 将A与C做左单旋，C被返回 */
    return SingleLeftRotation(A);
}

/*************************************/
/* 对称的右单旋与右-左双旋请自己实现 */
/*************************************/

/* 实现如下 */
AVLTree SingleRightRotation(AVLTree A) {
    /* 注意：A必须有一个右子结点B */
    /* 将A与B做右单旋，更新A与B的高度，返回新的根结点B */

    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Right), A->Height) + 1;

    return B;
}

AVLTree DoubleRightLeftRotation(AVLTree A) {
    /* 注意：A必须有一个右子结点B，且B必须有一个左子结点C */
    /* 将A、B与C做两次单旋，返回新的根结点C */

    /* 将B与C做左单旋，C被返回 */
    A->Right = SingleLeftRotation(A->Right);
    /* 将A与C做右单旋，C被返回 */
    return SingleRightRotation(A);
}

AVLTree Insert(AVLTree T, ElementType X) { 
    /* 将X插入AVL树T中，并且返回调整后的AVL树 */
    if (!T) { /* 若插入空树，则新建包含一个结点的树 */
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
    } /* if (插入空树) 结束 */

    else if (X < T->Data) {
        /* 插入T的左子树 */
        T->Left = Insert(T->Left, X);
        /* 如果需要左旋 */
        if (GetHeight(T->Left) - GetHeight(T->Right) == 2)
            if (X < T->Left->Data)
                T = SingleLeftRotation(T); /* 左单旋 */
            else
                T = DoubleLeftRightRotation(T); /* 左-右双旋 */
    } /* else if (插入左子树) 结束 */

    else if (X > T->Data) {
        /* 插入T的右子树 */
        T->Right = Insert(T->Right, X);
        /* 如果需要右旋 */
        if (GetHeight(T->Left) - GetHeight(T->Right) == -2)
            if (X > T->Right->Data)
                T = SingleRightRotation(T); /* 右单旋 */
            else
                T = DoubleRightLeftRotation(T); /* 右-左双旋 */
    } /* else if (插入右子树) 结束 */

    /* else X == T->Data，无须插入 */

    /* 别忘了更新树高 */
    T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;

    return T;
}

编程习题

1.是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出样例:

Yes
No
No

思路

两个序列是否对应相同搜索树的判别

1.分别建两棵搜索树的判别方法，根据两个序列分别建树，再判别树是否一样

2.不建树的判别方法

3.建一棵树，再判别其他序列是否与该树一致

这里考虑法三，建树就不赘述，关键在于判别序列。

方法：在树中按顺序搜索序列中的每个数，如果每次搜索所经过的结点在前面均出现过，则一致 ，否则（某次搜索中遇到前面未出现的结点），则不一致 。

AC code

#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode *Tree;
struct TreeNode {
    int v;
    Tree Left, Right;
    int flag;
};

Tree NewNode(int V) { //建立新结点
    Tree T = (Tree)malloc(sizeof(struct TreeNode));
    T->v = V;
    T->Left = T->Right = NULL;
    T->flag = 0;
    return T;
}

Tree Insert(Tree T, int V) { //插入新结点
    if (!T)                  //空树
        T = NewNode(V);
    else {
        if (V > T->v)
            T->Right = Insert(T->Right, V);
        else
            T->Left = Insert(T->Left, V);
    }
    return T;
}

Tree MakeTree(int N) { //建树
    Tree T;
    int i, V;
    scanf("%d", &V);
    T = NewNode(V); //根节点
    for (i = 1; i < N; i++) {
        scanf("%d", &V);
        T = Insert(T, V);
    }
    return T;
}

int check(Tree T, int V) {
    if (T->flag) { //访问过该节点
        if (V < T->v)
            return check(T->Left, V);
        else if (V > T->v)
            return check(T->Right, V);
        else
            return 0;
    } else { //没访问过该节点
        if (V == T->v) {
            T->flag = 1;
            return 1;
        } else
            return 0;
    }
}

int Judge(Tree T, int N) {
    //序列的每一个点进行check，若首次新访问的节点值一样，则一样
    int i, V, flag = 0;
    /* flag: 0代表目前还一致， 1代表已经不一致*/
    scanf("%d", &V);
    if (V != T->v)
        flag = 1;
    else
        T->flag = 1;
    for (i = 1; i < N; i++) {
        scanf("%d", &V); //保证读完
        if ((!flag) && (!check(T, V))) flag = 1;
    }
    if (flag)
        return 0;
    else
        return 1;
}

void ResetT(Tree T) { /* 清除T中各结点的flag标记 */
    if (T->Left) ResetT(T->Left);
    if (T->Right) ResetT(T->Right);
    T->flag = 0;
}

void FreeTree(Tree T) { /* 释放T的空间 */
    if (T->Left) FreeTree(T->Left);
    if (T->Right) FreeTree(T->Right);
    free(T);
}

int main() {
    int N, L, i;
    Tree T;
    scanf("%d", &N);
    while (N) {
        scanf("%d", &L);
        T = MakeTree(N);
        for (i = 0; i < L; i++) {
            if (Judge(T, N))
                printf("Yes\n");
            else
                printf("No\n");
            ResetT(T); /*清除T中的标记flag*/
        }
        FreeTree(T);
        scanf("%d", &N);
    }
    return 0;
}

测试点	提示	结果	分数	耗时	内存
0	sample 换顺序。有Yes，有No：根不同，子树根不同。树有单边、有双子树	答案正确	12	4 ms	316 KB
1	最大N，多组合	答案正确	8	3 ms	192 KB
2	N=1，只有1个节点	答案正确	3	3 ms	188 KB
3	卡只判断数字相对先后位置的错误算法	答案正确	2	3 ms	192 KB

2.Root of AVL Tree

2013年浙江大学计算机学院免试研究生上机考试真题

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N （≤20） which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the root of the resulting AVL tree in one line.

Sample Input 1:

5
88 70 61 96 120

Sample Output 1:

70

Sample Input 2:

7
88 70 61 96 120 90 65

Sample Output 2:

88

思路

基本的AVL树训练，套模板即可。

AC code

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

typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode {
    ElementType Data; /* 结点数据 */
    AVLTree Left;     /* 指向左子树 */
    AVLTree Right;    /* 指向右子树 */
    int Height;       /* 树高 */
};

int Max(int a, int b) { return a > b ? a : b; }

int GetHeight(Position P) {
    if (P == NULL)
        return -1;
    else
        return P->Height;
}

AVLTree SingleLeftRotation(AVLTree A) {
    /* 注意：A必须有一个左子结点B */
    /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */

    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Left), A->Height) + 1;

    return B;
}

AVLTree SingleRightRotation(AVLTree A) {
    /* 注意：A必须有一个右子结点B */
    /* 将A与B做右单旋，更新A与B的高度，返回新的根结点B */

    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Right), A->Height) + 1;

    return B;
}

AVLTree DoubleLeftRightRotation(AVLTree A) {
    /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
    /* 将A、B与C做两次单旋，返回新的根结点C */

    /* 将B与C做右单旋，C被返回 */
    A->Left = SingleRightRotation(A->Left);
    /* 将A与C做左单旋，C被返回 */
    return SingleLeftRotation(A);
}

AVLTree DoubleRightLeftRotation(AVLTree A) {
    /* 注意：A必须有一个右子结点B，且B必须有一个左子结点C */
    /* 将A、B与C做两次单旋，返回新的根结点C */

    /* 将B与C做左单旋，C被返回 */
    A->Right = SingleLeftRotation(A->Right);
    /* 将A与C做右单旋，C被返回 */
    return SingleRightRotation(A);
}

AVLTree Insert(AVLTree T, ElementType X) {
    /* 将X插入AVL树T中，并且返回调整后的AVL树 */
    if (!T) { /* 若插入空树，则新建包含一个结点的树 */
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
    } /* if (插入空树) 结束 */

    else if (X < T->Data) {
        /* 插入T的左子树 */
        T->Left = Insert(T->Left, X);
        /* 如果需要左旋 */
        if (GetHeight(T->Left) - GetHeight(T->Right) == 2)
            if (X < T->Left->Data)
                T = SingleLeftRotation(T); /* 左单旋 */
            else
                T = DoubleLeftRightRotation(T); /* 左-右双旋 */
    } /* else if (插入左子树) 结束 */

    else if (X > T->Data) {
        /* 插入T的右子树 */
        T->Right = Insert(T->Right, X);
        /* 如果需要右旋 */
        if (GetHeight(T->Left) - GetHeight(T->Right) == -2)
            if (X > T->Right->Data)
                T = SingleRightRotation(T); /* 右单旋 */
            else
                T = DoubleRightLeftRotation(T); /* 右-左双旋 */
    } /* else if (插入右子树) 结束 */

    /* else X == T->Data，无须插入 */

    /* 别忘了更新树高 */
    T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;

    return T;
}

AVLTree MakeTree() { //建树
    AVLTree A = NULL;
    int N, num;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &num);
        A = Insert(A, num);
    }
    return A;
}

void FreeTree(AVLTree A) { /* 释放A的空间 */
    if (A->Left) FreeTree(A->Left);
    if (A->Right) FreeTree(A->Right);
    free(A);
}

int main() {
    AVLTree A = MakeTree();
    printf("%d", A->Data);
    FreeTree(A);
    return 0;
}

测试点	提示	结果	分数	耗时	内存
0	fig 1 - LL	答案正确	4	5 ms	312 KB
1	fig 2 - RR	答案正确	4	5 ms	168 KB
2	fig 3 - RL	答案正确	4	4 ms	168 KB
3	fig 4 - LR	答案正确	4	4 ms	172 KB
4	深度LL旋转	答案正确	4	5 ms	172 KB
5	最大N，深度RL旋转	答案正确	4	4 ms	180 KB
6	最小N	答案正确	1	4 ms	180 KB

3.Complete Binary Search Tree

2013年秋季PAT甲级真题

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

思路

一句话概括题意：完全二叉树层序遍历。考虑利用数组，同时将输入序列进行排序，方便插入数组。

本题关键在于计算一个根节点左子树的规模，注意利用完全二叉树的性质即可！

AC code

#include <algorithm>
#include <cmath>
#include <cstdio>
#define MAXSIZE 2021
int A[MAXSIZE], T[MAXSIZE];

int min(int a, int b) {
    return (a < b) ? a : b;
}

bool cmp(int a, int b) {
    return a < b;
}

int pow(int a, int b) {
    int ans = 1;
    while (b && a) {
        if (b & 1)
            ans *= a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

int GetLeftLength(int n) {
    int H = (int)(log(n + 1) / log(2));
    int x = n + 1 - pow(2, H);
    x = min(x, pow(2, H - 1));
    return pow(2, H - 1) - 1 + x;
}

void solve(int ALeft, int ARight, int TRoot) {
    /* 初始调用为 solve(0, N-1, 0)*/
    int n = ARight - ALeft + 1;
    if (n == 0)
        return;
    int L = GetLeftLength(n); /* 计算出n个结点的树其左子树有多少个结点 */
    T[TRoot] = A[ALeft + L];
    int LeftTRoot = TRoot * 2 + 1;
    int RightTRoot = LeftTRoot + 1;
    solve(ALeft, ALeft + L - 1, LeftTRoot);
    solve(ALeft + L + 1, ARight, RightTRoot);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &A[i]);
    std::sort(A, A + n, cmp);
    solve(0, n - 1, 0);
    for (int i = 0; i < n - 1; ++i)
        printf("%d ", T[i]);
    printf("%d", T[n - 1]);
    return 0;
}

测试点	提示	结果	分数	耗时	内存
0	sample 换数字，但大小顺序不变	答案正确	18	4 ms	192 KB
1	完全平衡	答案正确	3	5 ms	308 KB
2	右边有余	答案正确	2	4 ms	344 KB
3	底层只多1个	答案正确	2	4 ms	192 KB
4	只有1个	答案正确	3	3 ms	188 KB
5	最大N随机	答案正确	2	5 ms	300 KB

4.二叉搜索树的操作集

本题要求实现给定二叉搜索树的5种常用操作。

函数接口定义：

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

• 函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针；
• 函数Delete将X从二叉搜索树BST中删除，并返回结果树的根结点指针；如果X不在树中，则打印一行Not Found并返回原树的根结点指针；
• 函数Find在二叉搜索树BST中找到X，返回该结点的指针；如果找不到则返回空指针；
• 函数FindMin返回二叉搜索树BST中最小元结点的指针；
• 函数FindMax返回二叉搜索树BST中最大元结点的指针。

裁判测试程序样例：

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

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("\n");

    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

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

输出样例：

Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9

思路

将先前的二叉树操作再实现一遍，注意修改模板代码使得接口一致。

AC code

BinTree Insert(BinTree BST, ElementType X) {
    if (!BST) { /* 若原树为空，生成并返回一个结点的二叉搜索树 */
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else { /* 开始找要插入元素的位置 */
        if (X < BST->Data)
            BST->Left = Insert(BST->Left, X); /*递归插入左子树*/
        else if (X > BST->Data)
            BST->Right = Insert(BST->Right, X); /*递归插入右子树*/
        /* else X已经存在，什么都不做 */
    }
    return BST;
}

BinTree Delete(BinTree BST, ElementType X) {
    Position Tmp;

    if (!BST)
        printf("Not Found\n");
    else {
        if (X < BST->Data)
            BST->Left = Delete(BST->Left, X); /* 从左子树递归删除 */
        else if (X > BST->Data)
            BST->Right = Delete(BST->Right, X); /* 从右子树递归删除 */
        else { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */
            if (BST->Left && BST->Right) {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin(BST->Right);
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete(BST->Right, BST->Data);
            } else { /* 被删除结点有一个或无子结点 */
                Tmp = BST;
                if (!BST->Left) /* 只有右孩子或无子结点 */
                    BST = BST->Right;
                else /* 只有左孩子 */
                    BST = BST->Left;
                free(Tmp);
            }
        }
    }
    return BST;
}

Position Find(BinTree BST, ElementType X) {
    if (!BST) return NULL;          /*查找失败*/
    if (X > BST->Data) 
        return Find(BST->Right, X);	/*在右子树中继续查找*/
    else if (X < BST->Data) 
        return Find(BST->Left, X); 	/*在左子树中继续查找*/
    else                           	/* X == BST->Data */
        return BST; /*查找成功， 返回结点的找到结点的地址*/
}

Position FindMin(BinTree BST){
	if (!BST) return NULL; 	/*空的二叉搜索树，返回NULL*/
	else if (!BST->Left)
		return BST; 		/*找到最左叶结点并返回*/
	else
		return FindMin(BST->Left); /*沿左分支继续查找*/
}

Position FindMax(BinTree BST){
	if (BST)
		while (BST->Right) BST = BST->Right;
	/*沿右分支继续查找，直到最右叶结点*/
	return BST;
}

测试点	提示	结果	分数	耗时	内存
0	sample等价	答案正确	18	4 ms	324 KB
1	左斜，Find小于最小、大于最大，delete小于最小、大于最大、头尾和中间	答案正确	4	3 ms	348 KB
2	右斜，Find小于最小、大于最大，delete小于最小、大于最大、头尾和中间	答案正确	4	3 ms	196 KB
3	只有1个结点，删除成空树	答案正确	2	4 ms	316 KB
4	空树	答案正确	2	3 ms	192 KB