爲什麼我的C++代碼無法刪除BST中的所有節點？

這應該是遍歷一個BST並刪除每個節點，包括根節點。然而，最後，我得到了「root還有一個左節點」的消息。爲什麼並非所有節點都被刪除？爲什麼我的C++代碼無法刪除BST中的所有節點？

void deleteTree() 
{ 
    deleteNode(root); 
    if(root->right) 
     cout << "root still has a right node" << endl; 
    if(root->left) 
     cout << "root still has a left node" << endl; 
    root = 0; 

} 

void deleteNode(node *p) 
{ 
    if(p->left) 
    { 
     deleteNode(p->left); 
     p->left = 0; 
    } 
    if(p->right) 
    { 
     deleteNode(p->right); 
     p->right = 0; 
    } 

    cout << "Deleting node containing " << p->data << endl; 
    delete p; 
}

來源

2010-02-11 neuromancer

您在結束（root）刪除p，然後試圖訪問deleteTree()，其內容在那裏root不再指向分配的內存。結果將是未定義的。

來源

2010-02-11 03:00:30

爲什麼當它檢查正確的節點時，它找不到任何東西，但是當它檢查左節點時它找到了什麼？ – neuromancer 2010-02-11 03:14:51

因爲'root'只是指向垃圾內存。其他結果可能包括只剩下，既不，也不會崩潰。 – Potatoswatter 2010-02-11 03:44:43

您正在刪除root。然後你的代碼試圖訪問它的內存。

你很好進入未定義的行爲土地。

來源

2010-02-11 03:01:11

刪除deleteNode後，您不應該取消root。使用調試器檢查爲什麼root->left非空。

來源

2010-02-11 03:01:19

對調試器的建議+1，但我認爲他會發現它實際上在函數返回時爲null。 – 2010-02-11 03:03:44

'root'肯定會被刪除，但'root-> left'必須有其他東西;也許在調試器周圍嗅探這個地址會揭示出一些東西...... – 2010-02-11 03:53:36

您正在查看root->left，因爲您已經刪除了root用戶，使其可用於新分配的塊。

來源

2010-02-11 03:02:17

-1

我只想改變樹本身，它會更容易對付它，那麼：

struct Node 
{ 
    Node(data_type data): mLeft(), mRight(), mData(data) {} 
    Node(const Node& rhs): mLeft(), mRight(), mData(rhs.mData) 
    { 
    if (rhs.mLeft.get()) mLeft.reset(new Node(*rhs.mLeft)); 
    if (rhs.right.get()) mRight.reset(new Node(*rhs.mRight)); 
    } 
    Node& operator=(Node rhs) 
    { 
    this->swap(rhs); 
    return *this; 
    } 
    ~Node() { } 

    void swap(Node& rhs) 
    { 
    using std::swap; 
    swap(mLeft, rhs.mLeft); 
    swap(mRight, rhs.mRight); 
    swap(mData, rhs.mData); 
    } 

    Node* left() const { return mLeft.get(); } 
    void left(std::auto_ptr<Node> node) { mLeft= node; } 

    Node* right() const { return mRight.get(); } 
    void right(std::auto_ptr<Node> node) { mRight = node; } 

    data_type& data() { return mData; } 
    const data_type& data() const { return mData; } 

private: 
    std::auto_ptr<Node> mLeft; 
    std::auto_ptr<Node> mRight; 
    data_type mData; 
};

由於是面向對象的，每個節點是負責處理它的內存。此外，在界面中使用std::auto_ptr可以清楚表明它擁有所有權。

請注意，它是爲深度複製量身定製的，其他任何需要boost::shared_ptr或其他等效方法。 std::auto_ptr讓你自己處理複製，沒有魔法。

這種設計比使用普通的C-struct更清潔，每個人都可以操縱資源。你仍然可以訪問通過訪問底層數據...但他們要注意不要發生未定義行爲...

當然，你仍然可以崩潰下來：

Node& node = ... 
delete node.left(); // haha

但如果C++可以防止意外的問題，它爲邪惡的代碼敞開大門。

來源

2010-02-11 13:22:01

爲什麼我的C++代碼無法刪除BST中的所有節點？

回答

相關問題