博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
C语言实现二叉搜索树
阅读量:242 次
发布时间:2019-03-01

本文共 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;};
  • 函数InsertX插入二叉搜索树BST并返回结果树的根结点指针;
  • 函数DeleteX从二叉搜索树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/

你可能感兴趣的文章