本文共 6195 字，大约阅读时间需要 20 分钟。

6-12 二叉搜索树的操作集 （30 point(s)）

本题要求实现给定二叉搜索树的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 
   
    #include 
    
     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
     
      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
     
    
   

输入样例：

105 8 6 2 4 1 0 10 9 756 3 10 0 555 7 0 10 3

输出样例：

Preorder: 5 2 1 0 4 8 6 7 10 96 is found3 is not found10 is found10 is the largest key0 is found0 is the smallest key5 is foundNot FoundInorder: 1 2 4 6 8 9

二叉搜索树是这样的数据结构：如果一个树的值比根大，则放在右儿子，比根小就放在左儿子

查找函数是很容易写的

递归形式(尾递归)：

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->Right, X);	else		return BST;}

非递归形式:

Position Find(BinTree BST, ElementType X){	while (BST)	{		if (X > BST->Data)			BST = BST->Right;		else if (X < BST->Data)			BST = BST->Left;		else			return BST;	}	return NULL;}

最大值必在最右边叶节点，最小值必在最右边叶子节点，所以可以写出找最大和最小数的函数

Position FindMin(BinTree BST){	while (BST)	{		if (!BST->Left)		{			return BST;		}		else		{			BST = BST->Left;		}	}	return NULL;}Position FindMax(BinTree BST){	while (BST)	{		if (!BST->Right)		{			return BST;		}		else		{			BST = BST->Right;		}	}	return NULL;}

二叉搜索树的插入总是插到叶节点的后面，用了递归的思想

BinTree Insert(BinTree BST, ElementType X){	if (!BST)	{		BinTree BST = (BinTree)malloc(sizeof(struct TNode));		BST->Data = X;		BST->Left = NULL;		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); // 递归插入右子数		}	}	return BST;}

二叉搜索树的删除有三种情况

1.被删除的是叶子节点，无左右儿子，直接删除，并把根节点设为空

2.被删除的有一个儿子，让这个点的父亲指向这个点儿子就行了

3.被删除的有左右儿子，用左子数的最大值或右子数的最小值来替代该节点，因为二叉搜索树左子数值都要小于这个根，右子数的值都大于这个根，这样替代之后是没有影响的，再删除这个节点就行了

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	{		// 如果被删除节点有子数，寻找下一个节点填充删除节点		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;   // 如果这个子数没有左儿子，将右儿子的指针赋给它，Free它			}			else if (!BST->Right)			{				BST = BST->Left;   // 如果这个子数没有右儿子，将左儿子的指针赋给它，Free它			}			free(Tmp);             // 这两种写法已经包括了有一个子数		}	}	return BST;}

完整代码

#include 
   
    #include 
    
     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_s("%d", &N);	for (i = 0; i
     
      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_s("%d", &N);	for (i = 0; i
      
       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); // 递归插入右子树		}	}	return BST;}Position Find(BinTree BST, ElementType X){	while (BST)	{		if (X > BST->Data)		{			BST = BST->Right;		}		else if (X < BST->Data)		{			BST = BST->Left;		}		else		{			return BST;		}	}	return NULL;}Position FindMin(BinTree BST){	while (BST)	{		if (!BST->Left)		{			return BST;		}		else		{			BST = BST->Left;		}	}	return NULL;}Position FindMax(BinTree BST){	while (BST)	{		if (!BST->Right)		{			return BST;		}		else		{			BST = BST->Right;		}	}	return NULL;}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	{		// 如果被删除节点有子数，寻找下一个节点填充删除节点		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;   // 如果这个子数没有左儿子，将右儿子的指针赋给它，Free它			}			else if (!BST->Right)			{				BST = BST->Left;   // 如果这个子数没有右儿子，将左儿子的指针赋给它，Free它			}			free(Tmp);             // 这两种写法已经包括了有一个子数		}	}	return BST;}void PreorderTraversal(BinTree BT){	if (!BT)		return;	printf(" %d", BT->Data);	PreorderTraversal(BT->Left);	PreorderTraversal(BT->Right);}void InorderTraversal(BinTree BT){	if (!BT)		return;	InorderTraversal(BT->Left);	printf(" %d", BT->Data);	InorderTraversal(BT->Right);}
      
     
    
   

转载地址：http://gxhv.baihongyu.com/