1

这应该遍历 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;
}
4

5 回答 5

6

您p在末尾删除 ( root)，然后尝试访问其内容deleteTree()，其中root不再指向分配的内存。结果将是不确定的。

于 2010-02-11T03:00:30.537 回答
2

你正在删除root. 然后你的代码试图访问它所在的内存。

你很喜欢那里的未定义行为领域。

于 2010-02-11T03:01:11.623 回答
2

root将其删除后不应取消引用deleteNode。使用调试器检查为什么root->left非空。

于 2010-02-11T03:01:19.610 回答
2

您正在查看root->left已删除 root 后，使其可用于新分配的块中。

于 2010-02-11T03:02:17.503 回答
-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-11T13:22:01.547 回答