2012-11-02 159 views
0

我有一個二叉搜索樹,當我嘗試執行刪除帶有單個子節點的情況時,您將刪除該節點並將其移動到位。我有它的代碼,但是每當我這樣做的時候它就會給我一個糟糕的指針。帶有一個孩子的二元搜索樹刪除節點

這是

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; 

我知道我分配錯了來自調試器的代碼段,有啥移動節點的正確方法?

回答

1

編輯:

不知道我怎麼錯過了它,但你刪除它之後,立刻使用root

編輯2: 您需要一個臨時的。

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

不,我需要它是XOR – wzsun

+0

@wzsun編輯我的回答 – James

+0

有人告訴我,你實際上必須先刪除它,讓我去與它一起,但如果你只是使用=重新分配那麼該節點會發生什麼?因爲它只是永遠存儲這個空間,你現在無法刪除它 – wzsun

0

這裏是一個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); 
    } 
} 
相關問題