Perché il codice C ++ mia non riescono a eliminare tutti i nodi nella mia BST?

Question

Questo dovrebbe attraversare una BST ed eliminare ogni nodo, tra cui il nodo principale. Tuttavia, alla fine, viene visualizzato il messaggio "radice ha ancora un nodo a sinistra." Perché non vengono cancellati tutti i nodi?

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

Il tuo sta eliminando p alla fine (root) e poi cercando di accedere al suo contenuto in deleteTree(), dove root non più punti di memoria allocata. Il risultato sta per essere undefined.

Answer 2

Si sta eliminando root. E poi il codice sta tentando di accedere alla memoria in cui è stato.

Sei così in terra indefinita-comportamento lì.

Answer 3

Non si dovrebbe risolvere il riferimento root dopo averlo eliminato in deleteNode. Utilizzare un debugger per ispezionare il motivo per cui root->left non è nullo.

Answer 4

Stai guardando root->left dopo aver già eliminato radice, rendendolo disponibile per l'utilizzo in un nuovo blocco allocato.

Answer 5

Vorrei semplicemente cambiare l'albero stesso, sarebbe più facile da affrontare poi:

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

Per essere orientato agli oggetti, ogni nodo è ora responsabile per la memoria che gestisce. Inoltre, utilizzando std::auto_ptr nell'interfaccia rende chiaro che ci vuole la proprietà.

Si noti che è stato adattato per il deep-copia, qualsiasi altro approccio che richiede boost::shared_ptr o equivalente. E sì std::auto_ptr lascia trattare con la copia da soli, nessuna magia lì.

Questo disegno è molto più pulito rispetto all'utilizzo di un C-struct pianura con tutti di essere in grado di manipolare le risorse. Hai ancora pieno accesso ai dati sottostanti tramite la funzione di accesso ... ma fate attenzione a non invocare un comportamento indefinito ...

Naturalmente, è ancora possibile mandare in crash il basso:

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

Ma se C ++ può proteggere contro problemi non intenzionali, lascia la porta aperta per il codice maligno.