二叉排序树的删除算法

傷城~ 2023-07-25 11:29 71阅读 0赞

关于二叉排序树的定义以及如何查找指定关键字的结点不再赘述，本篇文章主要讨论二叉排序树如何删除一个指定的结点。

当我们利用查找算法在树中找到了对应的结点的时候，可能会遇到三类情况。

第一类情况：

即将删除的结点是叶结点，将他删除以后，并不影响其他结点。（若为根结点，则整棵树为空，若不为根结点则其双亲结点对应的指针域指向空）  
下面的结点2就是这种情况。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70]  
第二类情况：

被删除的结点仅有一棵子树（左子树或者右子树），那么就将当前结点删除，如果当前结点是根结点，那么它子树的根结点，成为新的根结点。如果不是根结点，那么它双亲结点指向它的指针改为指向它的子树根结点。  
将根结点7删除以后，2便成了新的根结点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 2]  
这里值得注意的是，以上述为例，因为4是3的左子树，那么这棵树上所有的点必将大于3，所以5可以成为3的右子树。

最后一种情况：

待删除结点的左右子树俱全，这种情况可以有两种处理方法，以当前结点为根结点的子树的结点数据大小是，左子树 < 根 < 右子树  
如果要把根删除，则可以从左子树中找到一个最大的结点，或者右子树中一个最小的结点来替换根结点。

以上三种情况均需要记录删除结点的双亲结点。

下面开始根据思路撸代码：

typedef struct SearchNode{ 
        int data;
        struct SearchNode *left,*right;
        explicit SearchNode(int val):
        data(val),left(nullptr),right(nullptr){ }
    }SearchNode,*SearchTree;
    
    
    用于返回查找到的结点 parent指针记录双亲结点
    
    SearchNode * Order_Search(SearchNode * root,int val,SearchTree & parent){ 
        while(root){ 
            if(root->data == val)return root;
            parent = root;
            if(root->data > val)root = root->left;
            else root = root->right;
        }
        return nullptr;
    }
    用于返回下面用到的第一个中序遍历的结点
    SearchNode * Get_First_Mid(SearchNode * root){ 
    	while(root->left)root = root->left;
    	return root;
    }
    void Delete_Node(SearchNode & root,int val){ 
    	if(root == nullptr)return;
    	SearcNode * parent = nullptr;/* 记录待删除结点的双亲结点 */
    	SearchNode * target = Order_Search(root,val,parent);
    	if(!target)return;//如果待删除结点不存在，那么直接返回
    	待删除结点为叶结点，直接删除，并把双亲结点的指针指向空
    	if(!target->left && !target->right){ 
    		if(!parent){ 
    		//targetw为根结点
    		root = nullptr;
    		}else{ 
    			if(parent->left == target)parent->left = nullptr;
    			if(parent->right == target)parent->right = nullptr;
    		}
    		free(target);
    		return;
    	}
    	//当只有左子树的时候
    	if(!target->right && target->left){ 
    		//待删除结点是根结点
    		if(!parent)root = target->left;
    		else{ 
    			if(parent->left == target)parent->left = target->left;
    			if(parent->right == target)parent->right = target->left;
    		}
    		free(target);
    		return;
    	}
    	//当只有右子树的时候，与只有左子树逻辑是一样的
    	if(target->right && !target->left){ 
    		//待删除结点是根结点
    		if(!parent)root = target->right;
    		else{ 
    			if(parent->left == target)parent->left = target->right;
    			if(parent->right == target)parent->right = target->right;
    		}
    		free(target);
    		return;
    	}
    	最后一种情况便是左右孩子俱全
    	SearchNode * first = Get_First_Mid(target->right);//获得右子树中中序遍历的第一个结点
    	if(!parent)root = first;
    	else{ 
    		if(parent->left == target)parent->left = first;
    		else parent->right = first;
    	}
    	Delete_Node(target->right,first->val);//这是往下递归删除，直至回到第一类或者第二类情况
    	free(target);
    }

算法的难点在于三种情况的分析，并且每种情况都必须考虑，待删除结点是否为根节点。  
第三类情况是递归删除的思想，直到待删除结点变成第一种或者第二种情况。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70]: /images/20230528/703530d80a0a45da8162b06680af033f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 1]: /images/20230528/86325d95670b4ca09ac2007d56084143.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTUyNjIy_size_16_color_FFFFFF_t_70 2]: /images/20230528/d483904f87544167b034b47710721726.png