Освобождение памяти Двоичные деревья

Question

У меня есть функция, которая создает двоичное дерево (* build_tree) * (Хаффман).

Мне также нужна функция, которая освобождает память построить дерево выделено.

Это мой первый опыт работы с бинарными деревьями, поэтому я немного смущен. Должен ли я создать цикл, который проходит через каждый узел в дереве и удаляет его? Должен ли я рассматривать, является ли узел листом или родительским узлом?

void free_memory(NodePtr root) 
{ 
    delete root; 
} 

struct HuffmanNode 
{ 
    //some stuff 
    HuffmanNode *left; 
    HuffmanNode *right; 
}; 

бы признателен, если кто-то может помочь мне начать :)

Answer 1

Если вы используете смарт-указатели проблема будет решать сам. Если каждый узел содержит частный SP для своих детей, и вы удаляете узел, все его дети также будут освобождены. Очевидно, что ваш деструктор класса, который будет вызван SP при его очистке, должен будет освободить любые другие ресурсы, не назначенные RIIA, если они существуют.

class Node 
{ 
private: 
    std:unique_ptr<Node> left; 
    std:unique_ptr<Node> right; 
} 

Я использую std::unique_ptr<> здесь, потому что я предполагаю, что они являются частными и не подвергаются воздействию других частей программы. Если вы хотите, чтобы другие вещи ссылались на узлы, используя эти указатели, вы должны использовать std::shared_ptr<>.

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

class Node 
{ 
private: 
    NodePtr left; 
    NodePtr right; 

    ~Node() 
    { 
    delete left; 
    delete right; 

    // Delete any other resources allocated by the node. 
    } 
} 

Вы также можете сделать то, что @OldProgrammer предлагает и пересекает дерево снизу вверх, удаляя узлы, когда вы идете. Помните, что вы должны сделать это снизу вверх. Если вы сделали это сверху вниз, вы потеряете ссылку на (пока что) восстановленные дочерние узлы и утечку памяти. Как вы можете видеть, код для рекурсивного удаления (as referenced in @unluddite's answer) намного сложнее.

Накладные расходы памяти (что-либо) рекурсивно. См.: Is a recursive destructor for linked list, tree, etc. bad?. Если ваше дерево очень велико, тогда вы должны это рассмотреть и протестировать соответствующим образом.

Моя рекомендация будет для первого решения, если вы в порядке с использованием SP.

Answer 2

Если вы реализуете обход дерева после заказа и удаляете узел и данные на шаге процесса, вы убедитесь, что каждый узел вашего дерева посещен и данные удалены.

Вы можете увидеть рекурсивный и итеративный пример here с соответствующим кодом, воспроизводимым ниже.

Рекурсивный решение:

void postOrderTraversal(BinaryTree *p) {  
    if (!p) return; 
     postOrderTraversal(p->left); 
     postOrderTraversal(p->right); 

     // this is where we delete 
     delete p->data; 
     delete p; 
    } 

Одним из возможных итеративный решение:

void postOrderTraversalIterative(BinaryTree *root) { 
    if (!root) return; 
    stack<BinaryTree*> s; 
    s.push(root); 
    BinaryTree *prev = NULL; 
    while (!s.empty()) { 
     BinaryTree *curr = s.top(); 
     if (!prev || prev->left == curr || prev->right == curr) { 
      if (curr->left) 
       s.push(curr->left); 
      else if (curr->right) 
       s.push(curr->right); 
     } else if (curr->left == prev) { 
      if (curr->right) 
       s.push(curr->right); 
     } else { 
      // this is where we delete 
      delete curr->data; 
      delete curr; 
      s.pop(); 
     } 
     prev = curr; 
    } 
}