如何正确删除二叉树中的结点

本人很菜，这两天被二叉树搞的头很大
请问如何正确删除二叉树中的某一结点，我下面写的哪里错了，该怎么改呢？

//删除树中的某一节点
template<typename T>
void __fastcall TMyBTree<T>::DeleteBT(TNode<T>* src,TNode<T>* par)
{
    //TODO: Add your source code here
    //src代表所要删除的结点，par表示src的父结点
    TNode<T>* pTmp;                     //  保存当前节点
    TNode<T>* pTmp2;                    //   保存当前节点的父节点
    //TNode<T>* pTmp3;                    //   保存当前节点的右子节点
    if(NULL == src->lChild && NULL == src->rChild)   //此结点为叶子
    {
        if(m_pRoot == src)                 //表示src为根节点
            m_pRoot = NULL;
        else if(par->lChild == src)       //为父节点的左子树
            par->lChild = NULL;
        else                            //为父节点的右子树
            par->rChild = NULL;
        SAFEDEL(src);
    }
    else if(NULL == src->lChild)             //只有右子树
    {
        if(m_pRoot == src)                 //表示src为根节点
            m_pRoot = src->rChild;
        else if(par->lChild == src)       //为父节点的左子树
            par->lChild = src->rChild;
        else                            //为父节点的右子树
            par->rChild = src->rChild;
        SAFEDEL(src);
    }
    else if(NULL == src->rChild)        //只有左子树
    {
        if(m_pRoot == src)                 //表示src为根节点
            m_pRoot = src->lChild;
        else if(par->lChild == src)       //为父节点的左子树
            par->lChild = src->lChild;
        else                            //为父节点的右子树
            par->rChild = src->lChild;
        SAFEDEL(src);
    }
    else                                //左右子树都有
    {
        //遍历到src左子树的前驱节点上
        pTmp2 = src;
        pTmp = src->lChild;
        while(pTmp->rChild != NULL)
        {
            pTmp2 = pTmp;
            pTmp = pTmp->rChild;
        }
        if(m_pRoot == src)
            *m_pRoot = *pTmp2;        //将前驱节点赋给根节点
        else
            *src = *pTmp2;

        //if(pTmp->lChild != NULL)      
            pTmp2->rChild = pTmp->lChild;    //正确化前驱节点的父节点指针
        //else
        //    pTmp2->rChild = NULL;

        SAFEDEL(pTmp);
    }
    --m_nSize;
}

7 个解决方案

#1

根据我的经验看，肯定没有这么多else if的。

#2

引用 1 楼 healer_kx 的回复:

根据我的经验看，肯定没有这么多else if的。

是是是...书上写的我看不懂，是我自己想的...

#3

先用递归实现个简单的

#4

自己想的很好，但是书上的为什么不好呢？

#5

首先要考虑删除之后当前节点的左右孩子都怎么分配，这个问题解决了就都好办了。。。而且二叉树的算法大多都是递归比较容易。。。如果闲递归效率低也可以手动递归

#6

但是...我就是想请教下，我写的是哪里出错了，哪位大侠能花点时间教教我么？

#7

没时间看你的code，但我这有个可以用的你可以参考一下

   
template <class T>
void BinarySearchTree<T>::remove(T d){
	tree_node *curr,*parent;
	curr=root;
	parent=root;
	//Find the node
	while(curr!=NULL){
		if(curr->data==d)break;
		else if(curr->data>d){
			parent=curr;
			curr=curr->left;
		}
		else{
			parent=curr;
			curr=curr->right;
		}
	}

	if(curr==NULL){
		cout<<"Data not found!"<<endl;
		return;
	}
	//Delete a leaf node
	if(curr->left==NULL && curr->right==NULL){
		if(curr==root){
			delete curr;
			root=NULL;
		}
		else if(curr->data>parent->data){
			delete curr;
			parent->right=NULL;
		}
		else {
			delete curr;
			parent->left=NULL;
		}
	}
	//Delete a node with 2 children
	else if(curr->left!=NULL && curr->right!=NULL){
		//Find the smallest node on the right subtree
		tree_node *temp=curr->right;
		tree_node *temp_parent=curr;
		while(temp->left!=NULL){
			temp_parent=temp;
			temp=temp->left;
		}
		//The smallest is a leaf
		if(temp->left==NULL && temp->right==NULL){
			if(temp_parent!=curr){
				temp_parent->left=NULL;
			}
			else temp_parent->right=NULL;
			curr->data=temp->data;
			delete temp;
		}
		//The smallest is a node with only right subtree
		else {
			if(temp_parent!=curr){
				temp_parent->left=temp->right;
			}
			else temp_parent->right=temp->right;
			delete temp;
		}
	}
	//Delete a node with only one subtree
	else {
		if(curr->left!=NULL){
			if(curr->left->data > parent->data){
				parent->right=curr->left;
			}
			else parent->left=curr->left;
		}
		else{
			if(curr->right->data > parent->data){
				parent->right=curr->right;
			}
			else parent->left=curr->right;

		}
		delete curr;
	}

}