当前位置：首页 > biancheng >正文

二叉排序树（BST）删除结点算法详解之C语言版

biancheng 来源：原创 2022/10/5 17:28:45

一、算法原理

二叉排序树（Binary Sort Tree或 Binary Search Tree）又称二叉查找树，可以用来实现数据的快速查找，也方便数据的插入、删除等工作，因此适用于数据的动态查找。
二叉排序树是一棵二叉树，其左子树上的元素都小于树根，右子树上的元素都大于树根，所有的子树也满足这个性质。
在二叉排序树上删除某个结点，相对麻烦一点，因为删除结点后的二叉树仍旧是一棵二叉排序树。
删除结点主要包含了以下四种情形：
1）删除叶子结点
2）删除只有左子树的结点
3）删除只有右子树的结点
4）删除左右子树均不空的结点

针对第一种情形，直接删除树叶结点即可；
针对第二种情形，待删除结点的左子树树根替代待删除的结点即可；
针对第三种情形，待删除结点的右子树树根替代待删除的结点即可；
针对第四种情形，需要找到待删除结点的左子树最右侧的结点s，用其代替删除的结点即可，这是因为结点s是要删除结点的左子树的最大值所在的结点；
第一种到第三种情形操作相对简单，哪怕待删除的结点是树根。
第四种情形还包含了三类子情形，具体情况及相应的操作，如下图所示。
（一）s是p的左子树最右侧结点，同时是树叶。
在这里插入图片描述
算法如下：

sp->R = NULL;
p->data = s->data;
free(s);

（二）s是p的左子树树根，但不是树叶，即只有左子树，此时sq没有发挥作用。
在这里插入图片描述
算法如下：

p->L = s->L;
p->data = s->data;
free(s);

（三）s是p的左子树最右侧结点，但不是树叶，即只有左子树。
在这里插入图片描述
算法如下：

sp->R = s->L;
p->data = s->data;
free(s);

如上第四种情形的三种情况的操作，不管p是否是树根，做法均一致。当然，针对第四种情形，还有其它不同的处理手段，例如用其右子树的最左侧结点代替删除的结点也可以。

下面以具体案例给出上述四种情况下删除二叉排序树山结点的详细过程。图中标注的p指向的是待删除的结点，q指向了p的双亲结点。s指向了p的左子树上最右侧结点，sq指向了s的双亲结点。

Demo ：假设有二叉排序树如下图所示。
在这里插入图片描述
Step 1：删除树叶：
删除元素为27的结点，则首先需要定位到27所在的结点，并用指针p指向该结点，q指向其双亲结点，之后判断p的左右子树均为空，因此只需要直接释放该结点即可。
Step 2：删除只有左子树的结点
继续删除元素为20的结点，则首先需要定位到20所在的结点，并用指针p指向该结点，q指向其双亲结点。之后判断p的右子树为空，左子树不空，则将p的左子树链接到q的右子树并释放p指向的结点，得到如下结果。
在这里插入图片描述
Step 3：删除只有右子树的结点
继续删除元素为7的结点，则首先需要定位到7所在的结点，并用指针p指向该结点，q指向其双亲结点。之后判断p的左子树为空，右子树不空，则将p右子树链接到q的右子树并释放p指向的结点，得到如下结果。
在这里插入图片描述
Step 4：删除左右子树均不空的结点
继续删除元素为6的结点，则首先需要定位到6所在的结点，并用指针p指向该结点，q指向其双亲结点。之后判断p的左、右子树均不空，则将p左子树最右侧结点s的值5替换到p指向的结点，将sq的右子树置空，然后释放s指向的结点即可，得到如下结果。
在这里插入图片描述
Step 5：删除左右子树均不空的结点（处理不同于上一步，少了置空sq的右子树的步骤）
继续删除元素为5的结点，则首先需要定位到5所在的结点，并用指针p指向该结点，q指向其双亲结点。之后判断p的左、右子树均不空，则将p左子树最右侧结点s的值4替换到p指向的结点，然后释放s指向的结点即可，得到如下结果。
在这里插入图片描述
综上可以看出删除结点是比较麻烦的工作，而且即使是删除某一种情形的结点，其具体形式也可能不同。例如删除只有左子树的结点，处理的结果就是不同的，或者链接到双亲结点的左子树，或者链接到双亲的右子树。这都是要进行判断的，其实这里有一个比较明显的特征就是，左子树的结点是小于双亲的，右子树的结点是大于双亲的，据此就可以判断是链接到双亲的哪棵子树了。

二、二叉排序树删除结点算法的C程序

1. 二叉排序树删除结点函数

//在BST树上删除值为key的结点 
int BST_Deletion( BST *T, int key )
{
	int flag = 1;//删除成功失败的标志，初始化为成功。
	BST *p, *q, *s, *sq;//p指向待删除的结点，q指向p的双亲, s指向左右非空时的左子树最右侧的树叶 
	p = q = T;
	//找值为key的结点，即BST查找 
	while( p != NULL )
	{
		if( key == p->data )
		{
			break;
		}
		else if( key < p->data )
		{
			q = p;
			p = p->LChild;
		}
		else
		{
			q = p;
			p = p->RChild;
		}
	}
	if( p == NULL ) //此时在二叉排序树上没有找到目标结点 
	{
		flag = 0;
	}
	else//找到目标结点 
	{
		//1）如果是目标结点是树叶，则删除树叶
		if( p->LChild == NULL && p->RChild == NULL )
		{
			if( p->data == T->data )
			{
				T->data = NULLKEY;
			}
			else
			{
				if( p->data < q->data )
				{
					q->LChild = NULL;
				}
				else
				{
					q->RChild = NULL;
				}
				free( p );	
			} 
		}
		
		//2）删除只有左子树的结点
		else if( p->LChild != NULL && p->RChild == NULL )
		{
			//树根是待删除的结点 
			if( p->data == T->data ) //当前的参数T在函数内部不可以改变地址 ，只能改变T地址中的值
			{
				q = T->LChild;
				T->data = q->data;
				T->LChild = q->LChild;
				free(q);
			}
			else
			{
				if( p->data < q->data )
				{
					q->LChild = p->LChild;
				}
				else
				{
					q->RChild = p->LChild;
				}
				free( p );
			}
		}
		//3）删除只有右子树的结点
		else if( p->LChild == NULL && p->RChild != NULL )
		{
			//树根是待删除的结点
			if( p->data == T->data )//当前的参数T在函数内部不可以改变地址 ，只能改变T地址中的值 
			{
				q = T->RChild;
				T->data = q->data;
				T->RChild = q->RChild;
				free(q);
			}
			else
			{
				if( p->data < q->data )
				{
					q->LChild = p->RChild;
				}
				else
				{
					q->RChild = p->RChild;
				}
				free(p);
			}
		}
		//4）删除左右均非空的结点，需要看左子树的最右侧结点是树叶或者非树叶 
		//   此时处理不同于前面处理单分支的结点，只需要用目标结点s的值替换待删除结点p的值即可 
		else 
		{
			//首先找p的左子树的最右侧的结点 
			sq = p;
			s  = p->LChild;
			while( s->RChild != NULL ) 
			{
				sq = s;
				s  = s->RChild;
			}
			// 41）如果最右侧结点是树叶,将s的值赋值给p即可 
			if( s->LChild == NULL ) 
			{
				sq->RChild = NULL;//把s的双亲结点sq的右子树置空 
				p->data = s->data;
				free( s );//释放最右侧的树叶结点所占的空间 
			}
			else//42）最右侧结点不是树叶
			{
				// 421）s=p->LChild 没有右子树,此时sq还是指向了p,则只需要将s的左子树链接到p的左子树即可 
				if( sq->data == p->data )
				{
					p->LChild = s->LChild;
				}
				// 422）p->LChild 有右子树
				else
				{
					sq->RChild = s->LChild;	
				}
				p->data = s->data;
				free(s); 
			} 
		}
	}
	return flag; 
}

2.测试代码（仅供参考）

#include"stdio.h" 
#include"malloc.h"

#define NULLKEY  65535

//BST树的结点结构 
typedef struct node
{
	int data;
	struct node *LChild;
	struct node *RChild;
}BST;
void CreateBST( BST *T, int arr[], int n );
void InorderSearch( BST *T );
int SearchBST( BST *T, int key );
int BST_Deletion( BST *T, int key );

int main()
{
	
	int arr[] = { 18, 6, 20, 4, 7, 19, 27, 1, 5, 3, 14 };
	BST *T = ( BST * )malloc( sizeof( BST ) );
	CreateBST( T, arr, 11 );
	InorderSearch( T );
	printf( "\n" );
	
	int flag, key;
	key = 27;
	flag = BST_Deletion( T, key );//删除树叶 
	InorderSearch( T );
	printf( "\n" );
	
	key = 20;
	flag = BST_Deletion( T, key );//删除只有左子树的结点 
	InorderSearch( T );
	printf( "\n" );
	
	key = 7;
	flag = BST_Deletion( T, key );//删除只有右子树的结点
	InorderSearch( T );
	printf( "\n" );
	
	key = 6;
	flag = BST_Deletion( T, key );//删除左右子树均非空的结点（情形一） 
	InorderSearch( T );
	printf( "\n" );
	
	key = 18;
	flag = BST_Deletion( T, key );//删除左右子树均非空的树根 
	InorderSearch( T );
	printf( "\n" );
	
	key = 5;
	flag = BST_Deletion( T, key );//删除左右子树均非空的结点（情形二） 
	InorderSearch( T );
	printf( "\n" );
	
	
	printf( "\n" );
	int arr1[] = { 10 };
	BST *T1 = ( BST * )malloc( sizeof( BST ) );
	CreateBST( T1, arr1, 1 );
	InorderSearch( T1 );
	printf( "\n" );
	
	key = 10;
	flag = BST_Deletion( T1, key );//删除只有一个树根的BST树 
	if( T1->data == NULLKEY )//这个处理是和当前删除算法的参数有关。
	{
		printf( "the tree is empty.\n" );
	}
	printf( "\n" );
	
	int arr2[] = { 10 , 11, 12, 13, 14 };
	BST *T2 = ( BST * )malloc( sizeof( BST ) );
	CreateBST( T2, arr2, 5 );//只有左子树
	InorderSearch( T2 );
	printf( "\n" );
	
	key = 10;
	flag = BST_Deletion( T2, key );
	InorderSearch( T2 );
	printf( "\n" );
	
	int arr3[] = { 14 , 13, 12, 11, 10 };
	BST *T3 = ( BST * )malloc( sizeof( BST ) );
	CreateBST( T3, arr3, 5 );//只有右子树 
	InorderSearch( T3 );
	printf( "\n" );
	
	key = 14;
	flag = BST_Deletion( T3, key );
	InorderSearch( T3 );
	printf( "\n" );
	
	key = 15;
	flag = BST_Deletion( T3, key );
	if( flag == 0 ) 
	{
		printf( "%d is not on the BST\n", key );
	}
	return 0;
}//main
//根据已知的数组arr创建二叉排序树 
void CreateBST( BST *T, int arr[], int n ) 
{
	BST *s, *p, *q; 
	int i; 
	T->data = arr[0]; 
	T->LChild = NULL; 
	T->RChild = NULL; 
	for( i = 1; i < n; i++ ) 
	{
		s = (BST *)malloc( sizeof(BST) ); 
		s->data   = arr[i];
		s->LChild = NULL;
		s->RChild = NULL;
		p = T;
		while( p != NULL )
		{
			if( s->data == p->data )
			{
				printf( "%d existed.\n", s->data );
				q = NULL;
				break; 
			}
			q = p;
			if( s->data < p->data )
			{
				p = p->LChild;
			}
			else if( s->data > p->data )
			{
				p = p->RChild;			
			}
		} 
		if( q != NULL && s->data < q->data )
		{
			q->LChild = s;
		}
		else if( q != NULL && s->data > q->data )
		{
			q->RChild = s;
		}	
	}
}//CreateBST
//在BST树上查找元素key，返回查找成功与失败的标志 
int SearchBST( BST *T, int key )
{
	int flag = 0; //查找成功标志，初始化为失败 
	BST *p = T; 
	while( p != NULL )
	{
		if ( p->data == key )
		{
			flag = 1;
			break;
		}
		else if( key < p->data )
		{
			p = p->LChild;
		}
		else
		{
			p = p->RChild;
		}
	}
	return( flag );
}//SearchBST

//在BST树上删除值为key的结点 
int BST_Deletion( BST *T, int key )
{
	int flag = 1;//删除成功失败的标志，初始化为成功。
	BST *p, *q, *s, *sq;//p指向待删除的结点，q指向p的双亲, s指向左右非空时的左子树最右侧的树叶 
	p = q = T;
	//找值为key的结点，即BST查找 
	while( p != NULL )
	{
		if( key == p->data )
		{
			break;
		}
		else if( key < p->data )
		{
			q = p;
			p = p->LChild;
		}
		else
		{
			q = p;
			p = p->RChild;
		}
	}
	if( p == NULL ) //此时在二叉排序树上没有找到目标结点 
	{
		flag = 0;
	}
	else//找到目标结点 
	{
		//1）如果是目标结点是树叶，则删除树叶
		if( p->LChild == NULL && p->RChild == NULL )
		{
			if( p->data == T->data )
			{
				T->data = NULLKEY;
			}
			else
			{
				if( p->data < q->data )
				{
					q->LChild = NULL;
				}
				else
				{
					q->RChild = NULL;
				}
				free( p );	
			} 
		}
		
		//2）删除只有左子树的结点
		else if( p->LChild != NULL && p->RChild == NULL )
		{
			//树根是待删除的结点 
			if( p->data == T->data ) //当前的参数T在函数内部不可以改变地址 ，只能改变T地址中的值
			{
				q = T->LChild;
				T->data = q->data;
				T->LChild = q->LChild;
				free(q);
			}
			else
			{
				if( p->data < q->data )
				{
					q->LChild = p->LChild;
				}
				else
				{
					q->RChild = p->LChild;
				}
				free( p );
			}
		}
		//3）删除只有右子树的结点
		else if( p->LChild == NULL && p->RChild != NULL )
		{
			//树根是待删除的结点
			if( p->data == T->data )//当前的参数T在函数内部不可以改变地址 ，只能改变T地址中的值 
			{
				q = T->RChild;
				T->data = q->data;
				T->RChild = q->RChild;
				free(q);
			}
			else
			{
				if( p->data < q->data )
				{
					q->LChild = p->RChild;
				}
				else
				{
					q->RChild = p->RChild;
				}
				free(p);
			}
		}
		//4）删除左右均非空的结点，需要看左子树的最右侧结点是树叶或者非树叶 
		//   此时处理不同于前面处理单分支的结点，只需要用目标结点s的值替换待删除结点p的值即可 
		else 
		{
			//首先找p的左子树的最右侧的结点 
			sq = p;
			s  = p->LChild;
			while( s->RChild != NULL ) 
			{
				sq = s;
				s  = s->RChild;
			}
			// 41）如果最右侧结点是树叶,将s的值赋值给p即可 
			if( s->LChild == NULL ) 
			{
				sq->RChild = NULL;//把s的双亲结点sq的右子树置空 
				p->data = s->data;
				free( s );//释放最右侧的树叶结点所占的空间 
			}
			else//42）最右侧结点不是树叶
			{
				// 421）s=p->LChild 没有右子树,此时sq还是指向了p,则只需要将s的左子树链接到p的左子树即可 
				if( sq->data == p->data )
				{
					p->LChild = s->LChild;
				}
				// 422）p->LChild 有右子树
				else
				{
					sq->RChild = s->LChild;	
				}
				p->data = s->data;
				free(s); 
			} 
		}
	}
	return flag; 
}//BST_Deletion

//中序遍历二叉树-递归算法 
void InorderSearch( BST *T )
{
	if( T != NULL )
	{
		InorderSearch( T->LChild );
		if( T->LChild != NULL && T->RChild != NULL ) 
		{
			printf( "%5d/", T->data );//子树树根加个标识符/ 
		}
		else
		{
			printf( "%5d", T->data );
		}
		InorderSearch( T->RChild );
	} 
}//InorderSearch

3.运行结果
在这里插入图片描述

【Protobuf速成指南】Any类型的使用

协众信息三个层面帮你快速理解ui设计

大数据可视化开源平台，一招让数据资源活泛起来！

GEngine一个基于WebGPU的渲染引擎

44 最佳实践-性能最佳实践-裸设备映射

vue制作自己的组件库（仿ElementUI）

《树莓派4B家庭服务器搭建指南》第十六期：安装Calibre Web建立公网可访问私人电子书库

项目构建与部署

阿里云微服务引擎负责人李艳林：云原生网关当道，会带来哪些改变

LeetCode - 1 两数之和

一、算法原理

二、二叉排序树删除结点算法的C程序

相关文章：