бинарные деревья поиска код

Question

хочет написать деструктор для бинарного дерева поиска (его предполагается удалить все узлы дерева) вот что я получил до сих пор

virtual ~BST() { 
    BSTNode<Data>* node = root; 
    if (node == NULL){ 
    return; 
    }else if (node->left) { 
     while(node->left){ 
     delete node; 
     } 
    }else if (node->right){ 
     while(node->right) 
     delete node; 
    } 
     isize = 0; 
} 

я знаю, однако там что-то не так с код, как я могу его исправить

Answer 1

Когда вы делаете, например,

while(node->left){ 
    delete node; 
} 

Вы удаляете узел, но на самом деле не выполняете цикл до следующего. Поэтому в следующий раз в цикле node не будет NULL, поэтому вы разыщите нераспределенную структуру данных, которая является неопределенным поведением и может привести к сбою. И затем вы пытаетесь удалить тот же nodeснова, который по-прежнему является неопределенным поведением и может, безусловно, привести к сбою.

Вы также не удаляете как левый и правый узлы, только один из них связан с else.

Я предлагаю вам поставить правильный деструктор в BSTNode который удаляет свои собственные ребенок:

template<typename T> 
BSTNode<T>::~BSTNode() 
{ 
    delete left; 
    delete right; 
} 

Тогда деструктор дерева будет просто:

BST::~BST() 
{ 
    delete root; 
} 

Answer 2

Потерять else с. В противном случае, если дерево имеет left. right не удаляется.

Потерять while. Узлы должны иметь свои собственные деструкторы и должны удаляться рекурсивно.

Окончательно потеряйте if s. Потому что delete NULL действителен.

virtual ~BST() { 
    BSTNode<Data>* node = root; 
    if (node == NULL){ 
    return; 
    } 
    delete node->left; 
    delete node->right; 
    isize = 0; 
} 

Answer 3

void BST::deleteNode(BSTNode<Data> *node) { 
    if (node) { 
     deleteNode(node->left); 
     deleteNode(node->right); 
     delete node; 
    } 
} 

BST::~BST() { 
    deleteNode(root); 
}