c++ - 删除二叉树中具有两个子节点的节点

Question

所以这是我到目前为止的代码。我想我在很大程度上已经把逻辑搞砸了，但我被两个孩子困住了。我已经弄清楚我必须使用什么样的算法来让它工作（我已经用评论进行了注释在函数的底部），我只是不知道如何开始......谁能指出我正确的方向？

继承人我到目前为止：

void BinaryTree::remove(int data){
// Is the data valid?
if(data < 0){
    cerr << data << " is not valid.  Must be a positive integer value."  << endl;
}
else{
    // Find the node
    BinNode* loc = root;
    BinNode* parent = nullptr;
    bool found = false;
    while(!found && loc != nullptr){
        if(data > loc->data){
            parent = loc;
            loc = loc->right;
        }
        else if(data < loc->data){
            parent = loc;
            loc = loc->left;
        }
        else found = true;
    }

    // If there is a parent, take care of the pointer
    if(parent != nullptr){
        if(loc->data < parent->data)
            parent->left = nullptr;
        else if(loc->data > parent->data)
            parent->right = nullptr;
    }
    // If there are children, save pointers to them
    BinNode* leftChild = nullptr;
    BinNode* rightChild = nullptr;  
    if(loc->left != nullptr)
        leftChild = loc->left;
    if(loc->right != nullptr)
        rightChild = loc->right;

    // So now pointers to the children have been saved (if they exist) and
    // parent pointers have been taken care of (if they exist) the node can be deleted
    // If no children exist simply just delete the node and return
    delete loc;
    // If one child exists
    if(leftChild != nullptr || rightChild != nullptr){  
        if(leftChild != nullptr){
            if(leftChild->data < parent->data)
                parent->left = leftChild;
            else if(leftChild->data > parent->data)
                parent->right = leftChild;
        }
        else if(rightChild != nullptr){
            if(rightChild->data < parent->data)
                parent->left = rightChild;
            else if(rightChild->data > parent->data)
                parent->right = rightChild;
        }       
    }

    // Both children exist...this sucks.
    else if(leftChild != nullptr && rightChild != nullptr){
        // Find a minimum in the right subtree
        BinNode * min = root;
        BinNode * minParent = nullptr;
        while(min->left != nullptr){
            minParent = min;
            min = min->left;
        }
        // Replace value of the node to be removed with the found minimum
        loc = new BinNode(min->data);

        // Delete the remaining duplicate node
        if(minParent != nullptr)
            minParent->left = nullptr;
        delete min;
    }
}
}

Answer 1

我们到了。这似乎有效。如果有人对我如何优化这个或我需要解决的问题有任何建议，请说出来！谢谢！

void BinaryTree::remove(int data){
// Is the data valid?
if(data < 0){
    cerr << data << " is not valid.  Must be a positive integer value."  << endl;
}
else{
    // Find the node
    BinNode* loc = root;
    BinNode* parent = nullptr;
    bool found = false;
    while(!found && loc != nullptr){
        if(data > loc->data){
            parent = loc;
            loc = loc->right;
        }
        else if(data < loc->data){
            parent = loc;
            loc = loc->left;
        }
        else found = true;

    // If there are children, save pointers to them
    BinNode* leftChild = nullptr;
    BinNode* rightChild = nullptr;  
    if(loc->left != nullptr)
        leftChild = loc->left;
    if(loc->right != nullptr)
        rightChild = loc->right;

    // So now pointers to the children have been saved (if they exist) and
    // parent pointers have been taken care of (if they exist) the node can be deleted
    // If no children exist simply just delete the node and return

    // Check if two children exist
    if(leftChild != nullptr && rightChild != nullptr){

        // Find a minimum in the right subtree
        BinNode * min = loc->right;
        BinNode * minParent = loc;
        while(min->left != nullptr){
            minParent = min;
            min = min->left;
        }
        // Replace value of the node to be removed with the found minimum
        loc->data = min->data;

        // Delete the duplicate
        if(minParent != loc)
            minParent->left = nullptr;
        else minParent->right = nullptr;
        delete min;
    }

    // If one child exists
    // Need to handle if it is the root here
    // change root pointer to remaining child
    else if(leftChild != nullptr || rightChild != nullptr){ 
        // If there is a parent, take care of the pointer
        if(parent != nullptr){
            if(loc->data < parent->data)
                parent->left = nullptr;
            else if(loc->data > parent->data)
                parent->right = nullptr;

        // Now loc can be deleted
        delete loc;
        if(leftChild != nullptr){
            if(parent != nullptr){
                if(leftChild->data < parent->data)
                    parent->left = leftChild;
                else if(leftChild->data > parent->data)
                    parent->right = leftChild;
            }
            // If it is the root
            else{
                root = leftChild;
            }
        }
        else if(rightChild != nullptr){
            if(parent != nullptr){
                if(rightChild->data < parent->data)
                    parent->left = rightChild;
                else if(rightChild->data > parent->data)
                parent->right = rightChild;
            }
            // If it is the root
            else{
                root = rightChild;
            }
        }       
    }

    // If there are no children
    else if (leftChild == nullptr && rightChild == nullptr){
        // If there is a parent, take care of the pointer
        if(parent != nullptr){
            if(loc->data < parent->data)
                parent->left = nullptr;
            else if(loc->data > parent->data)
                parent->right = nullptr;
        }
        // If it is the root
        else 
            root = nullptr;
        delete loc;
    }
}