Почему моему коду C ++ не удается удалить все узлы в моем BST?

Question

Предполагается, что это пересечет BST и удалит каждый узел, включая корневой узел.Однако в конце я получаю сообщение "у root все еще есть левый узел". Почему не все узлы удалены?

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 после того, как вы уже удалили root, сделав его доступным для использования в новом выделенном блоке.

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 ++ может защитить от непреднамеренных проблем, это оставляет дверь открытой для вредоносного кода.