【数据结构】之二叉排序树的实现（C语言）

﹏ヽ暗。殇╰゛Y 2022-12-11 13:33 155阅读 0赞

### 文章目录 ###

*   *  二叉排序树
     *   *  二叉排序树的查找操作
         *  二叉排序树的插入操作
         *  二叉排序树的删除操作
     *  总结

如果我们要查找的数据集是有序线性表，并且是顺序存储的，查找可以用折半，插值，等查找算法来实现。可惜，因为有序，在插入和删除操作上，就需要耗费大量的时间。  
有没有一种既可以使得插入和删除的效率不错，又可以比较高效率的实现查找的算法呢？

## 二叉排序树 ##

**二叉排序树，又称为二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树。**

*  **若他的左子树不为空，则左子树上所有结点的值均小于他的根节点的值。**
 *  **若他的右子树不为空，则右子树上所有结点的值均大于他的根节点的值。**
 *  **他的左，右子树也分别为二叉排序树。**

从二叉树的定义也可以知道，它的前提是二叉树，然后它采用了递归的定义方法，再者，它的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。  
构造一颗儿二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。在一个有序数据集上的查找，速度总是要快于无序的数据集的。而二叉排序树这种非线性结构，也有利于插入和删除的实现。

### 二叉排序树的查找操作 ###

定义一个二叉树的结构

/* 二叉树的二叉链表结点结构定义 */
    typedef  struct BiTNode	/* 结点结构 */
    {
        
    	int data;	/* 结点数据 */
    	struct BiTNode *lchild, *rchild;	/* 左右孩子指针 */
    } BiTNode, *BiTree;

实现二叉排序树的查找

/* 递归查找二叉排序树T中是否存在key, */
    /* 指针f指向T的双亲，其初始调用值为NULL */
    /* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
    /* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
    Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) 
    {
          
    	if (!T)	/*  查找不成功 */
    	{
         
    		*p = f;  
    		return FALSE; 
    	}
    	else if (key==T->data) /*  查找成功 */
    	{
         
    		*p = T;  
    		return TRUE; 
    	} 
    	else if (key<T->data) 
    		return SearchBST(T->lchild, key, T, p);  /*  在左子树中继续查找 */
    	else  
    		return SearchBST(T->rchild, key, T, p);  /*  在右子树中继续查找 */
    }

### 二叉排序树的插入操作 ###

有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实就是将关键字放到树中合适的位置而已。

/*  当二叉排序树T中不存在关键字等于key的数据元素时， */
    /*  插入key并返回TRUE，否则返回FALSE */
    Status InsertBST(BiTree *T, int key) 
    {
          
    	BiTree p,s;
    	if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */
    	{
        
    		s = (BiTree)malloc(sizeof(BiTNode));
    		s->data = key;  
    		s->lchild = s->rchild = NULL;  
    		if (!p) 
    			*T = s;			/*  插入s为新的根结点 */
    		else if (key<p->data) 
    			p->lchild = s;	/*  插入s为左孩子 */
    		else 
    			p->rchild = s;  /*  插入s为右孩子 */
    		return TRUE;
    	} 
    	else 
    		return FALSE;  /*  树中已有关键字相同的结点，不再插入 */
    }

### 二叉排序树的删除操作 ###

对于删除情况我们要考虑多种情况，并不是那么容易的。我们不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性。  
如下图1-1所示，我们需要查找并删除入37,51,73,93，这些在二叉排序树中是叶子结点。那是很容易的，因为删除它，他们呢对于整棵树来说，其他的结点并没有受到影响。  
![在这里插入图片描述][20201001104231144.png_pic_center]

图1-1

对于要删除的结点只有左子树金额右子树的情况，相对也比较好解决，那就是结点删除之后，将它的左子树和右子树整个移动到删除结点的位置即可，可以理解为子承父业。如下图1-2所示，就是先删除35，和99结点，在删除58结点的变化图，删除完后，整个结构还是一个二叉排序树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center]

图1-2

但是对于要删除的结点既有左子树又有右子树的情况怎么办？如图1-3所示中的结点47若要删除，它的两个儿子以及子孙怎么处理了？  
![在这里插入图片描述][20201001105519239.png_pic_center]

图1-3

起初的想法，我们当47结点只有一个左子树，那么做法和一个左子树的操作一样，让35及它之下的结点成为58的左子树，然后再对47的右子树所有节点进行插入操作，图1-4所示，但是结点47的右子树共有5个子孙结点，这么做效率低下，而且还会导致整个二叉排序树的结构发生很大的变化，有可能会增加树的高度。

![在这里插入图片描述][20201001110937727.png_pic_center]

图1-4

观察观察，47的两个子树中能否找出一个结点可以替代47了？ 37或者48都可替代。  
为什么是37和48了？对的，因为他们正好是二叉排序树中比他小或比他大的最接近47的两个数。  
因此较好的办法就是，找到需要删除的结点p的直接前驱或者直接后继s，用s来替换结点p，然后在删除结点s，图1-5所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center 1]![在这里插入图片描述][20201001111716123.png_pic_center]

图1-5

根据对删除结点的三种情况的分析：

*  叶子节点
 *  仅有左或右子树的结点。
 *  左右子树都有的结点。

/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */
    Status Delete(BiTree *p)
    {
        
    	BiTree q,s;
    	if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */
    	{
        
    		q=*p; *p=(*p)->lchild; free(q);
    	}
    	else if((*p)->lchild==NULL) /* 只需重接它的右子树 */
    	{
        
    		q=*p; *p=(*p)->rchild; free(q);
    	}
    	else /* 左右子树均不空 */
    	{
        
    		q=*p; s=(*p)->lchild;
    		while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */
    		{
        
    			q=s;
    			s=s->rchild;
    		}
    		(*p)->data=s->data; /*  s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */
    		if(q!=*p)
    			q->rchild=s->lchild; /*  重接q的右子树 */ 
    		else
    			q->lchild=s->lchild; /*  重接q的左子树 */
    		free(s);
    	}
    	return TRUE;
    }
    
    /* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, */
    /* 并返回TRUE；否则返回FALSE。 */
    Status DeleteBST(BiTree *T,int key)
    {
         
    	if(!*T) /* 不存在关键字等于key的数据元素 */ 
    		return FALSE;
    	else
    	{
        
    		if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ 
    			return Delete(T);
    		else if (key<(*T)->data)
    			return DeleteBST(&(*T)->lchild,key);
    		else
    			return DeleteBST(&(*T)->rchild,key);
    		 
    	}
    }

## 总结 ##

二叉排序树是链接的方式存储的，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针。插入删除的时间性能可能比较好，而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为一次，即根结点就要是查找的结点，最多也不会超过树的深度，也就是说，二叉排序树的查找性能取决于二叉排序树的形状。问题就在于二叉排序树的形状是不确定的。

[20201001104231144.png_pic_center]: /images/20221123/f55ad2941ec344dfa0fac53f2c5be2c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ebbb7fc256ed44a389ae9cac25c3130a.png
[20201001105519239.png_pic_center]: /images/20221123/804a7eacf9a24c098be0ef6f7dbc9e75.png
[20201001110937727.png_pic_center]: /images/20221123/7b5813fb889c47f39e052356ae18ddb3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201001111707288.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70#pic_center
[20201001111716123.png_pic_center]: /images/20221123/9a151aab95d74e59a1decf67b697a231.png