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

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