Por que meu código C ++ não conseguem eliminar todos os nós no meu BST?
-
19-09-2019 - |
Pergunta
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;
}
Solução
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.
Outras dicas
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á.
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.
Você está navegando na root->left
depois que você já eliminado raiz, tornando-o disponível para uso em um novo bloco alocado.
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.