Por que meu código C ++ não conseguem eliminar todos os nós no meu BST?

Question

Isto é suposto para atravessar uma BST e excluir cada nó, incluindo o nó raiz. No entanto, no final, eu recebo a mensagem "root ainda tem um nó de esquerda." Por que todos nós não são excluídos?

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

Seu estiver excluindo p no final (root) e, em seguida, tentar acessar seu conteúdo em deleteTree(), onde root já não aponta para memória alocada. O resultado vai ser indefinido.

Answer 2

Você está excluindo root. E então o seu código está tentando memória de acesso onde estava.

Você é bem em terra-comportamento indefinido lá.

Answer 3

Você não deve excluir a referência root depois de excluí-lo em deleteNode. Use um depurador para inspecionar por root->left não é nulo.

Answer 4

Você está navegando na root->left depois que você já eliminado raiz, tornando-o disponível para uso em um novo bloco alocado.

Answer 5

Eu simplesmente mudar a própria árvore, seria mais fácil lidar com ele, então:

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

Por ser orientada a objetos, cada nó é agora responsável pela memória ele lida. Além disso, usando std::auto_ptr na interface deixa claro que ele toma posse.

Note que tem sido feito sob medida para deep-cópia, qualquer outra abordagem que requer boost::shared_ptr ou equivalente. E as folhas sim std::auto_ptr você lidar com a cópia por si mesmo, nenhuma mágica lá.

Este projeto é muito mais limpo do que usar um C-struct simples, com todos sendo capaz de manipular os recursos. Você ainda tem acesso completo aos dados subjacentes através do assessor ... mas tome cuidado para não invocar um comportamento indefinido ...

É claro, você ainda pode bater-lo para baixo:

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

Mas se C ++ pode proteger contra problemas não intencionais, ele deixa a porta aberta para o código mal.