在二叉排序树中删除节点

---

前言

在二叉排序树中删除节点的算法一直不是很明白，感觉很绕，花了三个小时算是彻底弄懂了。分享一下自己的心得。

个人在学习数据结构与算法中，有时候不理解的地方看别人的代码也是看不懂，自己的思路想要保存下来，比较清晰。

个人是个菜鸟，写的代码都很菜，希望大家不要介意。

---

代码如下

//二叉排序树的删除
Node* DeleteNode(BSTree bt, ElemType key) {
    
	if (bt == NULL) {
    
		return NULL;
	}
	//p指针保存当前节点。
	Node* p = bt;
	//pre指针保存p的父节点，方便后面指向p节点的做华子或右孩子
	Node* pre = NULL;
	//先在二叉搜索树中找到值为key的节点
	while (p != NULL) {
    
		if (p->data == key) {
    
			break;
		}
		else if (key < p->data) {
    
			pre = p;//保存p的前驱
			p = p->lchild;
		}
		else {
    
			pre = p;//保存p的前驱
			p = p->rchild;
		}
	}
	//如果没有找到，p指针为空，则返回根节点
	if (p == NULL) {
    
		return bt;
	}
	//当p指向的节点的左孩子为空时，将p节点的右孩子赋给p的父节点。
	if (p->lchild == NULL) {
    
		Node* temp = p;
		//三元表达式为判断p为pre的左孩子还是右孩子
		(pre->data < p->data ? pre->rchild : pre->lchild) = p->rchild;
		free(temp);
		temp = NULL;
	}
	//当p指向的节点的右孩子为空时，将p节点的左孩子赋给p的父节点。
	else if (p->rchild == NULL) {
    
		Node* temp = p;
		//三元表达式为判断p为pre的左孩子还是右孩子
		(pre->data < p->data ? pre->rchild : pre->lchild) = p->lchild;
		free(temp);
		temp = NULL;
	}
	//当左右孩子均不为空时，此处采用删除节点的左子树的最大值为替换。
	else {
    
		//post指针初始指向当前节点。实为max的父节点。
		Node* post = p;
		//max指针来找当前节点左子树的最大值。
		Node* max = p->lchild;
		//最后找下来max->rchild必为空。
		while (max->rchild != NULL) {
    
			post = max;
			max = max->rchild;
		}
		//将最大值替换删除节点。
		p->data = max->data;
		//处理最大值节点的后续子节点。
		//当post指针没有变时，说明最大节点就是post节点（也就是待删除节点p）的左孩子。那么对后续节点的处理就是直接把max的左孩子赋给post节点的左孩子（因为max节点的右孩子为空）。
		if (post == p) {
    
			post->lchild = max->lchild;
		}
		//当post指针和待删除节点p不同时，说明max在post的右子树里。那么对后续节点的处理就是直接把max的左孩子赋给post节点的右孩子（因为max节点的右孩子为空）。
		else {
    
			post->rchild = max->lchild;
		}
		//因为待删除节点已经被max的值覆盖了，max的孩子也已经被处理了，现在的max已经是没用的节点了，要free掉。
		free(max);
	}
	return bt;
}