！！！！！！！解析都在注释中，博主习惯打代码给出详细注释，这里就不做过多阐述，注释看不懂的话，直接留言！!!!!!!!!!

二叉排序树的结构声明

二叉排序树的创建

二叉排序树的节点删除

！！！！！！！解析都在注释中，博主习惯打代码给出详细注释，这里就不做过多阐述，注释看不懂的话，直接留言！!!!!!!!!!

二叉排序树的结构声明

typedef struct KeyNode
{
	int key;
	int otherData;
}keyNode,*PkeyNode; //设置关键字项和其他信息项
typedef struct BiTree
{
	KeyNode data;
	BiTree * Lchild;
	BiTree * Rchild; //指向左右孩子域
}BiTree,*PBiTree; //二叉树

二叉排序树的创建

void Insert_BST(PBiTree &T,int v) //插入元素V 每次都从树根节点向下遍历 
{
	if(!T)
	{
		printf("找到合适的位置，正在插入...\n");
		PBiTree new_node = (PBiTree)malloc(sizeof(BiTree));
		new_node->data.key = v;
		new_node->Lchild = NULL;
		new_node->Rchild = new_node->Lchild;
		T = new_node;
	}
	else if (v<T->data.key)
	{
		printf("%d 比节点值 %d 小 观察左节点\n",v,T->data.key);
		Insert_BST(T->Lchild,v);
	}
	else if (v>T->data.key)
	{
		printf("%d 比节点值 %d 大 观察节右节点\n",v,T->data.key);
		Insert_BST(T->Rchild,v);
	}
	//返回根节点
}
void Create_BST(PBiTree & T)
{
	T= NULL;
	int node;
	printf("输入根节点的值,-1结束\n");
	scanf_s("%d",&node);
	while (node!=-1)
	{
		Insert_BST(T,node);
		scanf_s("%d",&node);
	}
}

二叉排序树的节点删除

bool Dele_BiTNode(PBiTree & T,int key) //删除二叉排序树，要求删除节点后，排序树依然是有序的
{ //key -> 要删除的关键节点
	PBiTree f = NULL;
	PBiTree p = T; //
	PBiTree q = NULL;
	//根节点不为空
	while (p)
	{
		if (p->data.key==key) //找到当前节点，退出循环，记录p的位置
		{
			break;
		}
		//没有找到就一直向下找，用f记录删除节点的双亲节点
		f = p;
		if (key>p->data.key)
		{
			p = p->Rchild;
		}
		else
		{
			p = p->Lchild;
		}
	}
	 //退出循环，有两种情况
	 //①遍历结束都没有找到，此时p为空
	if(!p)
	{
	 return false;
	}
	//②成功找到该节点，但是需要判断删除的节点是否存在左子树or右子树
	//1.删除的节点同时存在左孩子和右孩子，此时应该找到删除节点的左孩子上中序遍历的最后一个节点
	//也就是左孩子中最大的节点S，这样才能保证替换后整体顺序不变
	//★★★ 那么，左孩子的最大节点一定是最右的节点所以肯定没有右孩子，这时就需要判断S节点是否有左节点
	//★★★如果S有左节点,需要设置一个临时变量q保存S的双亲，将S的左节点加到q的右孩子上
	//可以理解为痛失S孩子，含泪收养S的孩子
	q = p;
	if (p->Lchild!=NULL&&p->Rchild!=NULL)
	{
		//直接找p左子树上的最右节点
		PBiTree s = p->Lchild;
		while (s->Rchild)
		{
			q = s; //q是s的双亲
			s = s->Rchild;
		}
		p->data = s->data;
		if (q!=p) //q!=p 说明s不是p的直接后继节点
		{
			q->Rchild = s->Lchild; //痛失s节点含泪收养s的孩子
		}
		else
		{
			//q==p 说明s是p的直接后继
			q->Lchild = s->Lchild; //直接将s的孩子并入同p地址的左孩子
		}
		delete s;
		return true; 
		//删除节点同时存在左孩子和右孩子的程序结束，也是最难的部分
	}
	//2.删除的节点只有左子树
	if (!p->Rchild)
	{
		//重接左子树
		p = p->Lchild;
	}
	else if(!p->Lchild)
	{
		//重接右子树
		p = p->Rchild; //记住这里的f指向依然是p，此时p被覆盖，f指向迷失，需要用q重新拾回
	}
	//3.如果删除的是根节点
	if (!f)
	{
		T = p; //重新定义根节点
	}
	//这里就涉及到上面所说的指针迷失，需要为f重新指向删除节点后的左孩子or右孩子。
	else if(f->Lchild ==q)
	{
	//如果删除的是左子树，重接左子树
		f->Lchild = p;
	}
	else
	{
		f->Rchild = p; //重接右子树
	}
	delete q; //释放暂存指针
	return true;
}

实现效果