2016-12-30 64 views
0

我很難找出爲什麼我的樹的刪除功能「有點」刪除節點。當我打印結果時,「已刪除」節點顯示爲零。二元搜索樹刪除函數設置節點爲零而不是刪除

例如: 添加節點7,3,9,然後刪除節點9

輸入: 添加7,3,9 刪除3

輸出:0,7,9

void Tree::remove(int val) { 
Node* temp; 
if (root == nullptr) 
    {return;} 
if (val == root->val) 
{ 
    if (root->left == nullptr && root->right == nullptr){ //leaf node 
     delete root; 
     } 


    else{ 
     temp = root; 
     if (root->left != nullptr && root->right != nullptr){ //left and right children exist 

      if (root->left->val - val <= root->right->val - val){//left child is closer to value than right 
       int val_to_save = root->left->val; 
       root = root->left; 
       remove(val_to_save); 
       temp->val = val_to_save;//replace value with deleted node 
       root = temp;} 

      else{ 
       int val_to_save = root->right->val; 
       root = root->right; 
       std::cout << val_to_save << std::endl; 
       remove(val_to_save); 
       temp->val = val_to_save;//replace value with deleted node 
       root = temp;} 
     } 

     else{ // only one child, either left or right 
      if(root->left != nullptr){ //left child 
       temp->left = root->left; 
       delete temp;} 

      else{ //right child 
       temp->right = root->right; 
       delete temp;} 

     } 
    }   
} 

else{ //value does not match 
    temp = root; 
    if (val < root->val) 
     { 
     temp = temp->left; 
     remove(val); 
     root = temp; 
     } 

    else{ 
     root = root->right; 
     remove(val); 
     root = temp;}     
    } 
} 
+0

*我無法弄清楚爲什麼我的樹的刪除功能是「有點」刪除節點。* - 使用編譯器工具集隨附的調試程序,並查看您寫入的代碼在哪裏發散從你預期發生的事情。 – PaulMcKenzie

+0

當您刪除葉子時,請確保其父級的子級指針設置爲nullptr。也就是說,我認爲你還遠離實現正確的實施。 –

+0

是的,我在如何跟蹤當前節點及其子節點時遇到問題 – user6313136

回答

0

當您在C++中調用delete時,您將爲該給定對象釋放內存。但是,你實際上並不「聲明」它。例如,如果刪除root,它仍然知道root是一個節點。就像刪除溫度一樣。因此,您似乎正在成功刪除它,取消其價值並釋放其內存。但是,該對象仍然存在,但實例化爲空或字節形式的二進制0('\ 0')。當它打印一個\ 0時,結果顯示爲正常的0.

我假設你想讓你的答案打印爲7,9正確嗎?如果解釋你的問題錯了,讓我知道。

最佳

0

考慮有3節點,

[0] [7] [節點3] - > < - [node7] [3] [node9] - > < - [節點3] [9] [0]

,我們要刪除的節點3,

void Tree::remove(int val) 
{ 
    Node* root = head; // head is head node 
    if (root) 
    { 
     if (val == root->val) 
     { 
      if(root->left) 
       root->left->right = root->right; // making the right of 7 node as the right of 3 node, 
      if(root->right) 
       root->right->left = root->left; //making the left of 9 node as the left of 3 node, 
      delete root; 
      root = 0; 
     } 
    } 
} 
when we are deleting 7, if(root->right) will execute only, so the 0 (value of 7node->left) is assigned to 3node->left, 

when we are deleting 3, if(root->left) will execute , so the node9 (value of 3node->left) is assigned to 3node->left, 

when we are deleting 3, if(root->right) will execute , so the node7 (value of 3node->left) is assigned to 9node->left, 

when we are deleting 7, if(root->left) will execute only, so the 0 (value of 9node->right) is assigned to 3node->right,