遞歸地刪除每個節點在二叉樹

以下是我的代碼在二叉搜索樹遞歸地刪除每個節點：遞歸地刪除每個節點在二叉樹

template <class T> 
bool BST<T>::clear() 
{ 
    if(root == NULL) 
    { 
     cout << "Empty" << endl; 
     return false; 
    } 
    else 
    { 
     clearNodes(root); 
     return true; 
    } 

} 

template <class T> 
void BST<T>::clearNodes(BTNode<T> *cur) 
{ 
    if(cur == NULL) 
    { 
     return; 
    } 

    clearNodes(cur->left); 
    clearNodes(cur->right); 

    delete cur; 
}

在我的主要功能，當我嘗試打印出來的內容，檢查節點是否運行我的清除功能後刪除，不知何故，我在這裏遇到奇怪的顯示：

我可以知道我的節點實際上是通過上面的清除功能刪除？

感謝您的導遊！

來源

2015-08-30 user2611244

'delete'不會改變你的樹結構。你所做的只是釋放內存，留下無效節點的樹。另外，'delete'不會將指針設置爲NULL，這似乎是您的代碼依賴的。 – PaulMcKenzie

我假設「檢查節點是否被刪除」相當於clear()打印爲空。您的算法缺少重置已刪除節點的步驟。

修改後的版本是

template <class T> 
void BST<T>::clearNodes(BTNode<T>* &cur) //reference on pointer 
{ 
    if (cur==NULL) 
    { 
    return; 
    } 

    clearNodes(cur->left); 
    clearNodes(cur->right); 

delete cur; 
cur = NULL; //neccessary 
}

編輯：關於變更 一旦你觀察同節點問題沒有設置爲null解釋，第一次迭代將每次調用後設置有問題的節點，即

clearNodes(cur->right); 
cur->right = NULL;

這給責任來電，他的一個潛在的缺陷，因爲遲早呼叫者可能會忘記設置爲空或設置錯誤的值。因此，您要在clearNodes中設置。爲了修改函數內的指針，您需要傳遞指向它的指針或引用。在C++中，我更願意傳遞一個引用。因此簽名變成'

void BST<T>::clearNodes(BTNode<T>* &cur);

來源

2015-08-30 12:20:36 UmNyobe

嗨，UmNyobe，謝謝你的指導，我做到了。按照您的編輯，事情正常工作。順便說一下，我很好奇爲什麼2次更改是必要的？我覺得理解算法對我來說很重要，而不是單純地獲得答案。如果你能給我一些進一步的想法，我感謝你的努力。謝謝=） – user2611244

嗨UmNyobe。我想確保'cur'具有NULL子元素，並寫入'if（nullptr == cur-> left && nullptr == cur-> right）{delete cur; cur = nullptr; }'在後面部分，但是valgrind報告存在內存泄漏。顯然，如果條件是罪魁禍首。你能解釋爲什麼這是錯誤的嗎？ –

我猜測樹的根沒有設置爲Null，因此它保存垃圾，並且打印函數正在迭代隨機垃圾樹。確保在清除方法結束時將NULL設置爲樹根。

template <class T> 
bool BST<T>::clear() 
{ 
    if (root==NULL) 
    { 
    cout << "Empty" << endl; 
    return false; 
    } 

    else 
    { 
    clearNodes(root); 
    root = NULL; 
    return true; 
    }  

}

我假設你在打印時檢查樹根是否爲空，以確定樹是否爲空。

來源

2015-08-30 12:20:18

遞歸地刪除每個節點在二叉樹

回答

相關問題