带有一个孩子的二元搜索树删除节点

我有一个二叉搜索树，当我尝试执行删除带有单个子节点的情况时，您将删除该节点并将其移动到位。我有它的代码，但是每当我这样做的时候它就会给我一个糟糕的指针。带有一个孩子的二元搜索树删除节点

这是

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;

我知道我分配错了来自调试器的代码段，有啥移动节点的正确方法？

来源

2012-11-02 wzsun

编辑：

不知道我怎么错过了它，但你删除它之后，立刻使用root。

编辑2：您需要一个临时的。

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

来源

2012-11-02 02:18:18 James

不，我需要它是XOR – wzsun

@wzsun编辑我的回答 – James

有人告诉我，你实际上必须先删除它，让我去与它一起，但如果你只是使用=重新分配那么该节点会发生什么？因为它只是永远存储这个空间，你现在无法删除它 – wzsun

这里是一个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); 
    } 
}

来源

2016-09-07 14:20:24

带有一个孩子的二元搜索树删除节点

回答

相关问题