Как удалить двоичное дерево поиска из памяти?

Question

У меня есть BST, который является связанным списком на C++. Как я могу удалить все это из памяти? Это будет сделано из функции класса?

Answer 1

Выполнение послепорядка обхода дерева (например, посещение детей перед родителями) и удаление каждого узла при его посещении.

Независимо от того, связано ли это с классами, полностью зависит от вашей реализации.

Answer 2

С ограниченной информацией ....

Если вы выделили узлы с новыми или таНосом (или связанными с ними функциями), чем нужно, чтобы пройти через все узлы и бесплатно или удалить их.

Альтернативы положить shared_ptr's (and weak_ptr's to kill cyclics) в ваших отчислениях - если вы делаете это правильно, вы не должны освободить узлы вручную

Если вы использовали качественную реализацию, которые вы взяли в Интернете, чем при условии, что классы не просачиваются, вам не о чем беспокоиться.

Answer 3

Просто удалите детей:

struct TreeNode { 
    TreeNode *l, *r, *parent; 
    Data d; 

    TreeNode(TreeNode *p) { l = nullptr; r = nullptr; parent = p; } 
    TreeNode(TreeNode const &) = delete; 
    ~TreeNode() { 
     delete l; // delete does nothing if ptr is 0 
     delete r; // or recurses if there's an object 
    } 
}; 

или если вы используете unique_ptr или некоторые такие, что даже не нужно:

struct TreeNode { 
    unique_ptr<TreeNode> l, r; 
    TreeNode *parent; 
    Data d; 

    TreeNode(TreeNode *p) { l = nullptr; r = nullptr; parent = p; } 
    TreeNode(TreeNode const &) = delete; 
    ~TreeNode() = default; 
}; 

Answer 4

Используйте смарт-указатели и забыть об этом.

Answer 5

Если у вас есть доступ к самой связного списка, это кусок пирога:

// Making liberal assumptions about the kind of naming/coding conventions that might have been used... 
ListNode *currentNode = rootNode; 

while(currentNode != NULL) 
{ 
    ListNode *nextNode = currentNode->Next; 
    delete currentNode; 
    currentNode = nextNode; 
} 

rootNode = NULL; 

Если это обычай РЕАЛИЗАЦИЯ из BST, то это вполне может быть, как это работает внутри, если он имеет привязали себя к конкретной структуре данных.

Если у вас нет доступа к внутренним устройствам, тогда ответ Potatoswatter должен быть включен. Предполагая, что BST настроен по своему усмотрению, просто удаляя корневой узел, он должен автоматически удалить всю выделенную память, так как каждый родитель по дереву удалит его дочерние элементы.

Если вы спрашиваете, как идти о переборе через бинарное дерево вручную, то вы могли бы сделать следующий шаг: рекурсивного

void DeleteChildren(BSTNode *node) 
{ 
    // Recurse left down the tree... 
    if(node->HasLeftChild()) DeleteChildren(node->GetLeftChild()); 
    // Recurse right down the tree... 
    if(node->HasRightChild()) DeleteChildren(node->GetRightChild()); 

    // Clean up the data at this node. 
    node->ClearData(); // assume deletes internal data 

    // Free memory used by the node itself. 
    delete node; 
} 

// Call this from external code. 
DeleteChildren(rootNode); 

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