¿Por qué mi código C ++ no logran eliminar todos los nodos en mi BST?

Question

Esto se supone que atravesar una BST y eliminar todos los nodos, incluyendo el nodo raíz. Sin embargo, al final, me sale el mensaje "raíz todavía tiene un nodo izquierdo." ¿Por qué no se eliminan todos los nodos?

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

Los suprimiendo p al final (root) y luego tratar de acceder a su contenido en deleteTree(), donde root ya no apunta a la memoria asignada. El resultado va a ser indefinido.

Answer 2

Se va a eliminar root. Y luego su código está tratando de acceder a la memoria donde estaba.

Usted está bien definido en la tierra en el comportamiento allí.

Answer 3

No se debe eliminar la referencia root después de eliminar en deleteNode. Utilizar un depurador para inspeccionar qué root->left no es nulo.

Answer 4

Usted está mirando root->left después de que ya haya eliminado de raíz, haciendo que esté disponible para su uso en un nuevo bloque asignado.

Answer 5

Me basta con cambiar el árbol en sí, sería más fácil tratar con él, entonces:

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;
};

Al estar orientada a objetos, cada nodo es ahora responsable de la memoria que maneja. Además, el uso std::auto_ptr en la interfaz deja claro que se necesita la propiedad.

Tenga en cuenta que ha sido adaptado para deep-copia, cualquier otro enfoque que requiere boost::shared_ptr o equivalente. Y sí std::auto_ptr te deja hacer frente a la copia por sí mismo, sin la magia existe.

Este diseño es mucho más limpio que el uso de un C-struct llano con el que todos son capaces de manipular los recursos. Todavía tiene acceso completo a los datos subyacentes a través del descriptor de acceso ... pero tenga cuidado de no invocar un comportamiento indefinido ...

Por supuesto, todavía puede bloquearse hacia abajo:

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

Pero si C ++ puede proteger contra los problemas no deseados, deja la puerta abierta al código maligno.