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

时间:2022-08-17 10:12:28
本人很菜,这两天被二叉树搞的头很大
请问如何正确删除二叉树中的某一结点,我下面写的哪里错了,该怎么改呢?
//删除树中的某一节点
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;
}

}

#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;
}

}