二叉排序树（二叉查找树）的基本操作

雨点打透心脏的1/2处 2022-08-06 07:23 297阅读 0赞

二叉排序树的查找属于动态查找的范畴，根据查找过程中是否对表进行修改，可以把查找分为静态查找和动态查找。动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定的key值，若表中存在其关键字等于key的记录，则查找成功并返回，否则插入关键字等于key的记录。

二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：

（1）若它的左子树非空，则左子树上的所有结点的值均小于根节点的值；

（2）若它的右子树非空，则右子树上的所有结点的值均大于根节点的值；

（3）它的左右子树也分别为二叉排序树；

**1、二叉排序树的数据结构**

typedef struct node
    {
    	short key;
    	struct node *rchild,*lchild;
    } BSTNode,*BSTree;

**2、二叉排序树的插入和生成**

已知一个关键字值为key的节点s，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可，插入可以用一下方法。

（1）若二叉排序树为空树，则key称为二叉排序树的根;  
（2）若二叉排序树非空，则将key与二叉排序树的根比较，如果key值等于根节点，则停止插入；如果key值小于根节点的值，则将key插入左子树；如果key值大于根节点的值，则将key插入右子树；

二叉树的插入算法如下：

void InsertBST(BSTree* bst,short key)
    {
        BSTree s;
        if(*bst==NULL)    //递归结束条件;该结点为空时创建结点;
        {
            s=(BSTree)malloc(sizeof(BSTNode));
            s->key=key;
            s->lchild=NULL;
            s->rchild=NULL;
            *bst=s;
        }
        else if(key<(*bst)->key)
        {
            InsertBST(&((*bst)->lchild),key);
        }
        else if(key>(*bst)->key)
        {
            InsertBST(&((*bst)->rchild),key);
        }
    }
    
    /******************
    * 根据二叉排序树的插入算法可以创建一颗二叉排序树;
    ****************************/
    void CreateBST(BSTree* bst)
    {
        char key;
        *bst=NULL;
        scanf("%c",&key);
        while (key!='?')          //输入字符的结束是'？';
        {
            InsertBST(bst,key);
            scanf("%c",&key);
        }
    }

**3、二叉排序树的删除**

在二叉排序树中删除一个结点比插入一个结点要困难，除非是叶子结点，否则必须考虑部分链的对接，以保证删除一个结点后能使剩下的结点仍是一颗二叉排序树。

假设要删除的结点为P，其双亲结点为F，且不失一般性，并设结点P是结点F的左孩子（右孩子情况类似）。如下图所示：（注：下图截至数据结构书中）。![Center][]

下面分三种情况进行讨论：

（1）若P为叶子节点,删除P后只需修改双亲节点的指针即可;  
（2）如果P的左子树为空或者P的右子树为空,此时只需令其左右子树PL，PR成为其双亲结点F的左右子树即可;

（3）若P的左右子树均不为空，如图8.7（a）所示：此时有两种处理方法。

方法1：首先找到P结点在中序序列中的直接前驱S结点，如图8.7（b）所示，然后将P的左子树改为F的左子树，P的右子树改为S的右子树；

F->lchild=P->lchild;S->rchild=P->rchild;free(P);结果如图8.7（c）所示：因为P的右结点数值比S的数值大，故不会改变二叉排序树的性质;

方法2：首先找到P结点在中序序列中的直接前驱S结点，如图8.7（b）所示，然后用S结点的值代替P结点的值，再将S结点删除,原S结点的左子树改为双亲

结点Q结点的右子树；P->data=S->data;Q->rchild=S->lchild;free(S)。结果如图8.7（d）所示。

具体算法描述如下：

void DelBST(BSTree *t,short key)
    {
    	BSTNode *p,*f,*s,*q;
    
    	p=*t;
    	f=NULL;
    	while (p)				//查找关键字为key的待删节点;
    	{
    		if(p->key==key)		
    		{
    			break;			
    		}
    		f=p;				//f指向p节点的双亲节点;
    
    		if(p->key>key)
    		{
    			p=p->lchild;
    		}
    		else
    		{
    			p=p->rchild;
    		}
    	}
    
    	if(p==NULL)								//如果没有找到直接返回;
    	{
    		return;
    	}
    	if(f==NULL)								//如果p是原二叉排序树的根;
    	{
    		free(p);
    		*t=NULL;
    		return;
    	}
    
    	if(p->lchild==NULL&&p->rchild==NULL)	//如果p没有左右子树;
    	{
    		if(f->lchild==p)
    		{
    			f->lchild=NULL;
    		}
    		else
    		{
    			f->rchild=NULL;
    		}
    
    		free(p);
    	}
    	else if(p->lchild==NULL&&p->rchild!=NULL) //如果p的左子树为空,右子树不为空;
    	{
    		if(f->lchild==p)
    		{
    			f->lchild=p->rchild;   //把p的右子树链接到父亲的左链上;
    		}
    		else
    		{
    			f->rchild=p->rchild;	//把p的右子树链接到父亲的右链上;
    		}
    
    		free(p);
    	}
    	else if(p->lchild!=NULL&&p->rchild==NULL) //如果p的左子树不为空,右子树为空;
    	{
    		if(f->lchild==p)
    		{
    			f->lchild=p->lchild;   //把p的右子树链接到父亲的左链上;
    		}
    		else
    		{
    			f->rchild=p->lchild;	//把p的右子树链接到父亲的右链上;
    		}
    
    		free(p);
    	}
    	else if(p->lchild!=NULL&&p->rchild!=NULL)	//如果p的左右子树都不为空;
    	{
    		q=p;						
    		s=p->lchild;				//s指向p的左节点;
    		while (s->rchild)
    		{
    			q=s;
    			s=s->rchild;
    		}
    		p->key=s->key;				//把s节点的数据赋值给p节点;
    		if(p==q)				//说明待删除的p节点的左子节点下没有右结点;
    		{
    			q->lchild=s->lchild;	//把s节点的左子树链接到q的左节点下;
    		}
    		else
    		{
    			q->rchild=s->lchild;	//把s节点的左子树链接到q的右节点下;
    		}
    
    		free(s);
    	}
    }

**4.二叉排序树的查找**

由二叉排序树的定义可知,在二叉排序树上进行查找与二分查找类似。即：当二叉排序树不为空时，首先将给定值与根结点的关键值相比较，若相等，则查找成功。否则，将依据给定值和根节点关键值之间的大小关系，分别在左右子树上继续进行查找，其查找过程的算法如下：

BSTree SearchBST(BSTree bst,short key)
    {
    	if(bst==NULL)
    	{
    		return NULL;
    	}
    	if(bst->key==key)
    	{
    		return bst;
    	}
    	else if(bst->key>key)
    	{
    		return SearchBST(bst->lchild,key);
    	}
    	else 
    	{
    		return SearchBST(bst->rchild,key);
    	}
    }

**5、二叉排序树的查找分析**

根据二叉排序树的查找算法可以看出，二叉排序树的查找和二分查找类似，和关键字比较次数不超过树的深度，然而二分查找长度n的表判定树是唯一的，而含有n个结点二叉排序树却不唯一。对于含有同样关键字序列的一组结点，结点插入的先后次序不同，所构成的二叉排序树的形态和深度不同。而二叉排序树的平均查找长度ASL与二叉树的形态相关，二叉排序树的各分支越均衡，树的深度越浅，其平均查找长度ASL越小。

就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无需移动大量的结点。因此，对于需要经常做插入、删除、查找运算的表，宜采用二叉排序树，因此二叉排序树又称为二叉查找树。

**6、总结**

上面是我在精读数据结构时，对二叉排序树的一点总结，也参考了相关的书籍，望各位读者多多指教。

[Center]: /images/20220806/cf5a9d4ec64d4659a2dd078ff2966d2d.png