二叉排序树C/C++代码实现

阳光穿透心脏的1/2处 2023-02-21 06:43 24阅读 0赞

## 二叉排序树(二叉查找树): ##

二叉排序树的一个重要性质：中序遍历一棵二叉 树时可以得到一个结点值递增的有序序列。

对于需要经常进行插入、 删除和查找运算的表，采用二叉排序树比较好

## 查找： ##

若二叉排序树为空，则查找失败，返回空指针。  
若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：  
1,若key等于T->data.key , 则查找成功,返回根结点地址；  
2,若key小于T->data.key, 则递归查找左子树；  
3,若key大于T->data.key , 则递归查找右子树。

时间复杂度O(log2n)

## 插入，创建： ##

若二叉排序树为空则直接插入为根结点，否则key小于根结点的话递归调用左子树插入，大于则递归调用右子树插入。

一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列， 构造树的过 程即为对无序序列进行排序的过程。

输入的结点顺序不同，构造的二叉树不同，性能也不同  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

## 删除： ##

删除分三种情况：  
**1，被删除结点为叶子结点：**  
不会破坏整棵树的结构，只需将双亲结点指针置为NULL即可。

**2，被删除结点只有左子树或只有右子树：**  
只需将被删除结点的左子树或右子树接到被删除结点的双亲结点相应处即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]  
**3，被删除结点既有左子树又有右子树：**  
由于中序遍历特点知：被删除结点前驱或后继只可能有一个孩子或没有孩子的情况。故直接前驱（或直接后继） 替代被删除结点, 然后再从二叉排序树中删去它的直接前驱（或直接后继）。  
![在这里插入图片描述][20200629161118810.png]

## 代码如下： ##

以该图为例:![在这里插入图片描述][20200629161229209.png]

#include<stdio.h>
    
    typedef int KeyType;
    typedef int InfoType;
    //二叉排序树的二叉链表储存
    typedef struct
    {
        
    	KeyType key;
    	InfoType otherinfo;
    }ElemType;
    typedef struct BSTNode
    {
        
    	ElemType data;
    	struct BSTNode *lchild, *rchild;
    }BSTNode, *BSTree;
    
    //二叉排序树的插入
    void InsertBST(BSTree &T, ElemType e)
    {
        
    	BSTree S;
    	if (!T)				//如果是空树，直接插入根结点
    	{
        
    		S = new BSTNode;
    		S->data = e;
    		S->lchild = S->rchild = NULL;
    		T = S;
    	}
    	else if (e.key < T->data.key)	//如果小于根结点则往左继续递归
    	{
        
    		InsertBST(T->lchild, e);
    	}
    	else if (e.key > T->data.key)	//如果大于根结点则往右继续递归
    	{
        
    		InsertBST(T->rchild, e);
    	}
    
    }
    //二叉排序树的创建
    void CreatBST(BSTree &T)
    {
        
    	T = NULL;
    	//递归调用插入算法即可，此处用直接赋值代替输入
    	ElemType e;
    	e.key = 45;
    	InsertBST(T, e);
    
    	e.key = 24;
    	InsertBST(T, e);
    
    	e.key = 53;
    	InsertBST(T, e);
    
    	e.key = 12;
    	InsertBST(T, e);
    
    	e.key = 37;
    	InsertBST(T, e);
    
    	e.key = 93;
    	InsertBST(T, e);
    }
    
    //二叉排序树的查找
    //若查找成功， 则返回指向该数据元素结点的指针,否则返回空指针
    BSTree SearchBST(BSTree T, KeyType key)
    {
        
    	if (!T || key == T->data.key)   return T;		//找到或树为空
    	else if (key < T->data.key)
    	{
        
    		return SearchBST(T->lchild, key);
    	}
    	else
    	{
        
    		return SearchBST(T->rchild, key);
    	}
    }
    
    
    //二叉排序树的删除
    void DeleteBST(BSTree &T, KeyType key)
    {
        
    	BSTree q = NULL;
    	BSTree p = T;
    	BSTree f = NULL;
    	while (p)				//查找要删除的结点p和该结点的双亲f
    	{
        
    		if (p->data.key == key) break;
    		f = p;
    		if (p->data.key > key)  p = p->lchild;
    		else p = p->rchild;
    	}
    	if (!p)  return;		//没找到
    
    	//------------------------------------------------------
    	//1，当被删结点左右子树都不为空时
    	if ((p->lchild) && (p->rchild))
    	{
        
    		//寻找p的中序遍历前序来替换p的位置，即左子树的最右边的结点
    		BSTree s = p->lchild;	//s为要替换p的结点
    		BSTree q = p;
    		while (s->rchild)
    		{
        
    			q = s;				//这里q是指向s的双亲结点
    			s = s->rchild;
    		}
    		//替换结点
    		p->data = s->data;
    		if (q != p)
    		{
        
    			q->rchild = s->lchild;			//前驱s只能有左子树，或左子树也没有，此时s->lchild为NULL
    		}
    		else
    		{
        
    			q->lchild = s->lchild;			//即q指向p时，直接把p的左子树置为NULL
    		}
    		delete s;				//此时s结点的位置已经被他的左孩子或NULL覆盖，释放指针
    		return;					//这种情况直接退出即可，不需要重接删除结点的左右孩子
    	}
    
    	//------------------------------------------------------
    	//2，当被删结点只有左子树或只有右子树时
    	else if (p->lchild)
    	{
        
    		q = p;					//q指向要删除的结点
    		p = p->lchild;			//有左孩子，让p指向它的左孩子
    	}
    	else if (p->rchild)
    	{
        
    		q = p;					//q指向要删除的结点
    		p = p->rchild;			//有左孩子，让p指向它的左孩子
    	}
    
    
    	//------------------------------------------------------
    	//3,当被删结点是叶子结点时
    	else if (!p->lchild &&!p->rchild)
    	{
        
    		q = p;
    		p = NULL;
    	}
    
    	//------------------------------------------------------
    	//重接删除结点的左孩子或右孩子
    	if (!f)	T = p;			//删除的是根结点
    	else if (q == f->lchild) f->lchild = p;
    	else if (q == f->rchild) f->rchild = p;
    	delete q;
    }
    
    
    
    
    //先序遍历输出二叉排序树
    void println(BSTree T)
    {
        
    	if (T)
    	{
        
    
    		if (T->lchild != NULL && T->rchild != NULL)		//有两个孩子时
    		{
        
    			printf("data:%d,lchild:%d,rchlid:%d\n", T->data.key, T->lchild->data.key, T->rchild->data.key);
    		}
    		else if (T->lchild != NULL)						//只有左孩子时
    		{
        
    			printf("data:%d,lchild:%d\n", T->data.key, T->lchild->data.key);
    		}
    		else if (T->rchild != NULL)						//只有右孩子时
    		{
        
    			printf("data:%d,rchlid:%d\n", T->data.key, T->rchild->data.key);
    		}
    		else											//叶子结点
    		{
        
    			printf("data(叶子):%d\n", T->data.key);
    		}
    
    		//递归
    		println(T->lchild);
    		println(T->rchild);
    	}
    }
    
    
    int main() 
    {
        
    	BSTree T;
    	CreatBST(T);
    
    	println(T);
    
    	//查找24
    	BSTree R = SearchBST(T, 24);
    	//如果返回的不是空指针则证明找到
    	if (!R)
    	{
        
    		printf("\n对不起，没找到！\n");
    	}
    	else
    	{
        
    		printf("\n已找到：%d\n", R->data.key);
    	}
    
    
    	//测试删除24
    	printf("\n删除后:\n");
    	DeleteBST(T, 24);
    	println(T);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629153913573.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200629161042203.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[20200629161118810.png]: https://img-blog.csdnimg.cn/20200629161118810.png
[20200629161229209.png]: https://img-blog.csdnimg.cn/20200629161229209.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200629161318889.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70