6-12 二叉搜索树的操作集(点击查看原题)
本题要求实现给定二叉搜索树的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
实现代码
/*
二叉搜索树（BST），又叫做二叉排序树，有以下特点：
1.若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值
2.若它的右子树不空，则右子树上所有节点的值均小于它的根节点的值
3.它的左、右子树均为二叉排序树
因为二叉排序树的性质，我们就可以很方便地使用递归
*/
BinTree Insert( BinTree BST, ElementType X )
{
BinTree t;
t =(BinTree)malloc(sizeof(struct TNode)); //先malloc一个新节点
t->Data = X; //把X赋值给新节点的数据域
t->Left=NULL; //左右子树均为空
t->Right=NULL;
if(BST==NULL) //当树为空时
{
BST=t; //把新节点直接赋值给空树
}
else if(BST->Data>X) //当节点数值大于X时
{
BST->Left=Insert(BST->Left,X); //递归节点的左子树，因为左子树要小于它的根节点
} //特别要注意：要写成BST->left=的形式，这样到时候直接返回BST就是树的根节点指针
else if(BST->Data<X) //当数值大于X时
{
BST->Right=Insert(BST->Right,X); //递归节点的右子树，同上写成BST->left形式，我因为这一直显示错误改了好几次才发现
}
return BST; //直接返回树的根节点指针
}
BinTree Delete( BinTree BST, ElementType X ) //查找目标值时有四种情况
{
if(BST==NULL) // 1.树为空树
{
printf("Not Found\n");
return NULL;
}
else if(BST->Data>X) // 2.数值大于X
{
BST->Left = Delete(BST->Left,X); //同上使用递归，并注意BST->left形式
}
else if(BST->Data<X) // 3.数值小于X
{
BST->Right = Delete(BST->Right,X);
}
else // 4.找到目标值时，此时删除又有四种情况
{ // 第四种情况是删除叶子节点时，可当做特殊的第一或第二种情况
BinTree q,s;
if(BST->Right==NULL) // 1.BST只有左子树情况
{
q = BST;
BST = BST->Left;
free(q);
}
else if(BST->Left==NULL) // 2.BST只有右子树情况
{
q = BST;
BST = BST->Right;
free(q);
}
else //3.左右子树同时存在时 ，具体分析看思路分析
{
q = BST;
s = BST->Left;
while(s->Right)
{
q = s;
s = s->Right;
}
BST->Data = s->Data;
if(q!=BST)
{
q->Right = s->Left; //s的右子树已经循环遍历完了，只可能存在左子树了
}
else
{
q->Left = s->Left;
}
free(s);
}
}
return BST;
}
Position Find( BinTree BST, ElementType X )
{
if(BST==NULL)
{
return NULL;
}
else if(BST->Data==X)
{
return BST;
}
else if(BST->Data>X) //数值大于X
{
return Find(BST->Left,X);
}
else //数值小于X
{
return Find(BST->Right,X);
}
}
Position FindMin( BinTree BST ) //最小节点一定是二叉搜索树的最左边的节点
{
if(BST==NULL)
{
return NULL;
}
while(BST->Left) //当BST存在左子树时循环遍历，找到最左的那个子树
{
BST=BST->Left;
}
return BST;
}
Position FindMax( BinTree BST ) //最大节点一定是最右边的那个子树
{
if(BST==NULL)
{
return NULL;
}
while(BST->Right) //右子树存在时循环遍历，找到最右的子树
{
BST=BST->Right;
}
return BST;
}
解题思路
二叉搜索树（BST），又叫做二叉排序树，有以下特点： 1.若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值 2.若它的右子树不空，则右子树上所有节点的值均小于它的根节点的值 3.它的左、右子树均为二叉排序树 因为二叉排序树的性质，我们就可以很方便地使用递归。
关于删除操作的分析，请看下面《大话数据结构》中的讲解，写的是真详细（多图预警）。
