为什么我的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中的所有节点？

回答

相关问题