二叉搜索树的定义及相关操作

桃扇骨 2022-02-03 05:29 240阅读 0赞

### 二叉搜索树 ###

*   *   *  定义
         *  操作
         *   *   *  二叉搜索树的查找操作Find
                 *  查找最大和最小元素
                 *  二叉搜索树的插入
                 *  二叉搜索树的删除

### 定义 ###

二叉搜索树(BST)是一棵特殊的而擦函数，可以为空，它满足一下性质：  
**1.** 非空左子树的**所有**键值**小于**其根结点的键值  
**2.** 非空右子树的**所有**键值**大于**其根结点的键值  
**3.** 左、右字数都是二叉搜索树  
**4.** 由此可看出二叉树的中序遍历可以得到一个从小到大的输出序列

### 操作 ###

##### 二叉搜索树的查找操作Find #####

**递归实现**

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->Left, X);  //在左子树中递归查找
    	else  //x==BST->Data
    	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 //X==BST->Data
    			break;  //在当前结点查找成功，跳出循环 
    	}
    	return BST; //返回找到的结点地址，或是UNLL 
    }

##### 查找最大和最小元素 #####

根据二叉搜索树的性质，最小元素一定是在树的最左分支的端结点上。所谓最左分支的端结点，是指最左分支上没有孩子的结点。而最大元素一定是最右分支的端结点上。如下图所示。这就使得比查找函数更简单，只要从根结点开始，当其不为空时，沿着左分支或右分支逐个判断各结点的指针，知道遇到空指针为止。从左分支逐层退下来查找到的是最小元素，从右分支找到的是最大元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]  
**查找最小元素的递归实现**

Position FindMin(BinTree BST) //最小元素在最左端点 
    {
        
    	if(!BST) return NULL; //空的二叉搜索树，返回NULL
    	else if(!BST->Left) return BST; //找到最左端并返回
    	else
    	return FindMin(BST->Left); //沿左分支递归查找 
    }

**查找最大元素的迭代实现**

Position FindMin(BinTree BST)
    {
        
    	if(BST)
    	while(BST->Right)
    		BST=BST->Right; //沿右分支一直向下，知道最右端点
    	return BST; 
    }

##### 二叉搜索树的插入 #####

将元素X插入二叉搜索树BST中关键是要找到元素应该插入的位置。位置的确定可以利用与查找函数Find类似的方法，如果在树BST中找到X，说明要插入的元素已经存在，可放弃插入操作。如果没有找到X，查找终止的位置就是X要插入的位置。  
如图所示插入元素35，先做查找操作，按照上面介绍的查找算法，查找将终止在键值为33的叶结点处，将元素35作为此终止结点的右孩子就完成了新元素的插入。  
**代码**

BinTree Insert(BinTree BST, ElementType X)
    {
        
    	if(!BST)  //若原树为空，生成并返回一个结点的二叉搜索树
    	{
        
    		BST=(BinTree)malloc(sizeof(struct TNode));
    		BST->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) //递归插入右子树 
    		//else X已经存在，什么都不做 
    	}
    	return BST;
    }

##### 二叉搜索树的删除 #####

二叉搜索树的删除操作比较复杂，要删除结点在树中的位置决定了操作的方法，有三种情况需要考虑：  
**1. 要删除的是叶结点**  
出现这种情况可以直接删除，然后再修改其父结点的指针，置空即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 1]  
**2.如果眼删除的结点只有一个孩子结点（该结点不一定是叶结点，也可以是子树的根），删除之前需要改变其父结点的指针，指向要删除结点的孩子结点，如图所示**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]: /images/20220203/da2d8424dd8a4d5f807bbfd6c7507201.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 1]: /images/20220203/c7131d85da4048af9c246ac2147f362f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70 2]: /images/20220203/6d492a7fdcfe4779bb8bc40676d68fed.png