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

Question

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

Answer 1

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

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 2

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

// 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);

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

Answer 3

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

То, имеет ли это какое-либо отношение к классам, полностью зависит от вашей реализации.

Answer 4

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

Answer 5

С предоставленной ограниченной информацией ....

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

Альтернативой может быть shared_ptr (и weak_ptr для уничтожения циклических) в ваших выделениях - при условии, что вы сделаете это правильно, вам не придется освобождать узлы вручную

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