binary-search-tree - 具有一个孩子的二叉搜索树删除节点

Question

我有一个二叉搜索树，当我尝试删除具有单个子节点的节点时，删除该节点并将子节点移动到它的位置。我有它的代码，但是每当我这样做时，它都会给我一个错误的指针。

这是代码段

else if((root->Left != NULL) != (root->Right != NULL)){ //Checks if it's a on child node
    if(root->Left != NULL){ //If it has a left child, attempts to move the left child to existing node
        delete root;
        root = root->Left;
    }
    else{ //If it is right child, attempts to move right child to existing node
        delete root;
        root = root->Right;
    }
}

该结构具有值

DATA_TYPE Value;
TreeNode* Left;
TreeNode* Right;

我知道我从调试器中分配错误，那么移动节点的正确方法是什么？

Answer 1

编辑：

不知道我是怎么错过的，但您root删除后立即使用。

Edit2：你需要一个临时的。

TreeNode* temp = root->Right;
delete root;
root = temp;

Answer 2

这是该方法的Java实现

public void removeHalfNodes () {

    if ( root == null ) return;
    if ( root.left == null && root.right == null ) return;
    if ( root.left == null && root.right != null ) root = root.right;
    else if ( root.left != null && root.right == null ) 
        root = root.left;

    removeHalfNodesRec ( root );
}

public void removeHalfNodesRec ( BinaryTreeNode node ) {

    if ( node.left != null ) {
        if ( node.left.left == null && node.left.right != null )
            node.left = node.left.right;
        else if ( node.left.right == null && node.left.left != null )
            node.left = node.left.left;

        removeHalfNodesRec ( node.left );
    }

    if ( node.right != null ) {
        if ( node.right.left == null && node.right.right != null )
            node.right = node.right.right;
        else if ( node.right.right == null && node.right.left != null )
            node.right = node.right.left;

        removeHalfNodesRec ( node.right );
    }
}