为什么我的C ++代码，无法删除所有节点在我的BST？

Question

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

Answer 1

您在端（p）删除root然后试图访问在deleteTree()，其中root不再指向分配的存储器的内容。其结果将是不确定的。

Answer 2

您要删除root。然后你的代码试图访问存储在哪里。

你顺利进入未定义行为的土地在那里。

Answer 3

您不应该你root删除后提领deleteNode。使用调试器来检查为什么root->left是非空的。

Answer 4

您正在寻找root->left你已经删除了根之后，使其可用于新分配的块使用。

Answer 5

我只想改变树本身，它会更容易对付它，然后：

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 ++可以防止意外的问题，它敞开了大门，以邪恶的代码。