C++ 二叉排序树的删除 学习笔记

首先  我们把

这样一个排序二叉树列出来举例 

我们要对它的某一个节点删除  在删除的过程中我们要面临三种情况

1.

要删除的节点没有孩子  

这种是最简单的  不需要任何操作  直接删除即可

2.

要删除的节点只有一个孩子

这种情况我们一般的处理方式就是让要删除的节点的孩子直接连接爷爷节点

3.

要删除的节点有两个孩子

这种事最复杂的  我们可以通过替换节点中的值的方法  :

找到要删除的节点的 左 的 最右节点    或   找到要删除的节点的 右 的 最左节点

(因为这两个节点是最接近要删除的节点的值的)

然后替换    要删除的节点和找到的节点的   值

然后删除的找到的节点即可

下面开始对我们的代码进行编写

首先我们承接上文中对排序二叉树的添加  遍历  查找的代码

C++ 数据结构 二叉顺序表的添加 学习笔记_van9527的博客-CSDN博客

在主函数中 我们定义了一个这样的二叉树

 

BST* pBoot = nullptr;
	BST* pFather = nullptr;
	AddBST(pBoot, 34);
	AddBST(pBoot, 12);
	AddBST(pBoot, 50);
	AddBST(pBoot, 40);
	AddBST(pBoot, 17);
	AddBST(pBoot, 8);
	AddBST(pBoot, 21);

之后我们开始对删除函数进行编写

参数:   根节点  ,  要删除的节点的值

void  DeleteBST(BST*& rpBoot, int id)

首先我们在函数中定义了一个父亲节点用来记录要删除的节点的父亲节点

这个节点我们在处理    被删除的节点时只有一个孩子的节点    时会用到

BST* pFather = nullptr;

    //找到要删除的节点和他的父亲

利用查找函数找到要删除的节点   没找到就直接结束删除函数
    BST* pDel = Serch(rpBoot, id, pFather);
    if (pDel == NULL)
    {
        cout << "没找到要删除的节点" << endl;
        return;
    }

//判断是不是根   先判断一下   是的话就对根节点进行修改   

在这里  我们用到了 三目运算符  
    if (pFather == NULL)
    {
        
        rpBoot = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;

    }

//分析孩子情况
      //两个孩子
        //找到最左的右  或最右边左  替换掉要删除的节点
    if (pDel->pLeft != NULL && pDel->pRight != NULL)
    {
        BST* pMark = pDel;
        pFather = pDel;
        pDel = pDel->pLeft;
        while (pDel->pRight != NULL)
        {
            pFather = pDel;
            pDel = pDel->pRight;
        }

        pMark->id = pDel->id;

    }

上述代码中pMark是用来替换节点的值的

   //一个孩子或没有孩子

if (pDel->pLeft == NULL || pDel->pRight == NULL)
    {

         //一个孩子

/./如果要删除的节点时它父亲的左(右 )  就执行孙节点的爷节点的连接
            if (pFather->pLeft == pDel)
            {
                pFather->pLeft= pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
            }
            if (pFather->pRight== pDel)
            {
                pFather->pRight = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
            }
        
        
        if (pDel->pLeft == NULL && pDel->pRight == NULL)
        {
            //没有孩子

        }
        

         
    }

//删除
        delete pDel;
        pDel = NULL;

函数编写完成

之后我们对函数进行测试

主函数中我们

DeleteBST(pBoot,12);

然后对二叉树进行遍历

输出结果

 

完整代码如下

#include
#include
using namespace std;
//二叉排序树中不允许出现相同的值的节点
struct BST
{
	int id;
	BST* pLeft;
	BST* pRight;

};

void AddBST(BST*& rpBoot, int id)
{
	BST* pTemp = new BST;
	pTemp->id = id;
	pTemp->pLeft = nullptr;
	pTemp->pRight = nullptr;


	if (rpBoot == NULL)
	{
		rpBoot = pTemp;
		return;
	}
	BST* pMark = rpBoot;


	while (pMark != NULL)
	{
		if (pTemp->id < pMark->id)
		{

			if (pMark->pLeft == NULL)
			{
				pMark->pLeft = pTemp;
				return;

			}
			pMark = pMark->pLeft;
		}
		else if (pTemp->id > pMark->id)
		{

			if (pMark->pRight == NULL)
			{
				pMark->pRight = pTemp;
				return;

			}
			pMark = pMark->pRight;
		}
		else if (pTemp->id == pMark->id)
		{
			cout << "添加节点的值错误" << endl;
			return;
		}



	}





}


BST* Serch(BST* rpBoot, int id, BST*& Father)
{

	BST* fMark = rpBoot;
	if (rpBoot == NULL)
	{
		cout << "二叉树为空" << endl;
		return 0;
	}



	while (rpBoot != NULL)
	{
		if (id == rpBoot->id)
		{
			cout << "找到了" << endl;
			Father = fMark;
			return rpBoot;
		}
		if (id < rpBoot->id)
		{


			fMark = rpBoot;
			rpBoot = rpBoot->pLeft;
		}
		else if (id > rpBoot->id)
		{


			fMark = rpBoot;
			rpBoot = rpBoot->pRight;
		}



	}
	cout << "没有" << endl;
	return NULL;





}


void  DeleteBST(BST*& rpBoot, int id)
{

	BST* pFather = nullptr;

	//找到要删除的节点和他的父亲
	BST* pDel = Serch(rpBoot, id, pFather);
	if (pDel == NULL)
	{
		cout << "没找到要删除的节点" << endl;
		return;
	}


	//判断是不是根
	if (pFather == NULL)
	{
		
		rpBoot = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;

	}


	//分析孩子情况
	  //两个孩子
		//找到最左的右  或最右边左  替换掉要删除的节点
	if (pDel->pLeft != NULL && pDel->pRight != NULL)
	{
		BST* pMark = pDel;
		pFather = pDel;
		pDel = pDel->pLeft;
		while (pDel->pRight != NULL)
		{
			pFather = pDel;
			pDel = pDel->pRight;
		}

		pMark->id = pDel->id;

	}


	if (pDel->pLeft == NULL || pDel->pRight == NULL)
	{

			//一个孩子
			if (pFather->pLeft == pDel)
			{
				pFather->pLeft= pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
			}
			if (pFather->pRight== pDel)
			{
				pFather->pRight = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
			}
		
		
		if (pDel->pLeft == NULL && pDel->pRight == NULL)
		{
			//没有孩子



		}
		

		
	}
	    //删除
		delete pDel;
		pDel = NULL;
		

	
}


void zhongxubianli(BST * pRoot)
	
{
		if (NULL == pRoot)
		{
			return;
		}


		stackst;

		while (1)
		{

			while (pRoot)
			{

				st.push(pRoot);

				pRoot = pRoot->pLeft;

			}

			if (st.empty() == true)
			{
				cout << endl;
				return;
			}

			pRoot = st.top();
			st.pop();

			cout << pRoot->id << " ";
			pRoot = pRoot->pRight;





		}



	
}





int main()
{
	BST* pBoot = nullptr;
	BST* pFather = nullptr;
	AddBST(pBoot, 34);
	AddBST(pBoot, 12);
	AddBST(pBoot, 50);
	AddBST(pBoot, 40);
	AddBST(pBoot, 17);
	AddBST(pBoot, 8);
	AddBST(pBoot, 21);
	zhongxubianli(pBoot);

	
	

	DeleteBST(pBoot,12);
	zhongxubianli(pBoot);
	return 0;
}

 

暑期编程PK赛 得CSDN机械键盘等精美礼品！