1

Помогите найти утечку памяти в следующей реализации бинарного дерева. Может кому не лень копаться в таком куске кода)

template <typename T>
class Node
{
 private:
    T data;
    Node<T> *left, *right;
    bool flag;
    friend class Tree<T>;
 public:
    Node(): flag(false), left(NULL), right(NULL){}
    ~Node{if(left) delete left; if(right)delete right}
};

template <typename T>
class Tree
{
 private:
    Node<T>* head;
    Node<T>* AddNode(Node<T>*, T);
    void ViewTree(Node<T>*);
    void DestroyTree(Node<T>*);
 public:
    Tree();
    ~Tree();
    void View();
    void Add(T);
};

template <typename T>
Tree<T>::Tree(): head(NULL){}

template <typename T>
Tree<T>::~Tree()
{
 DestroyTree(head);
}

template <typename T>
void Tree<T>::View()
{
 ViewTree(head);
}

template <typename T>
void Tree<T>::Add(T obj)
{
 head = AddNode(head, obj);
}

template <typename T>
Node<T>* Tree<T>::AddNode(Node<T>* root, T obj)
{
 if(root == NULL)
 {
  root = new Node<T>;
  root->data = obj;
  root->flag = true;
 }
 else
 {
  if(obj < root->data)
  {
   root->left = AddNode(root->left, obj);
  } 
  else 
  {
   root->right = AddNode(root->right, obj);
  }
 }
 return root;
}

template <typename T>
void Tree<T>::ViewTree(Node<T> *root)
{
 if(root->left)
 {
  ViewTree(root->left);
 }
 if(root->flag) cout << root->data << endl;
 if(root->right)
 {
  ViewTree(root->right);
 }
}

template <typename T>
void Tree<T>::DestroyTree(Node<T> *root)
{
 if(root)
 {
  DestroyTree(root->left);
  DestroyTree(root->right);
  delete root;
 }
}

int main()
{
 Tree<int> *tree = new Tree<int>;
 tree->Add(5);
 tree->Add(4);
 tree->Add(2);
 tree->View();
 delete tree;
}

Спасибо, если кому не лень в этом копаться

4
  • что не все утечки ещё отловили?
    – sercxjo
    8 июн 2012 в 20:37
  • В том посте неправильно исходник написал
    – carapuz
    8 июн 2012 в 20:41
  • вы в старом посте заменили исходник, так что теперь между ними нет разницы
    – sercxjo
    8 июн 2012 в 20:45
  • ну delete root вы добавили, теперь утечек я не вижу
    – sercxjo
    8 июн 2012 в 20:47

1 ответ 1

3

У вас не утечка, а даже наоборот. Вы удаляете рекурсивно все поддерево и в DestroyTree и при удалении каждого узла. Чтобы все было правильно, надо либо убрать рекурсивные вызовы из деструктора ~Node, т.е. просто использовать деструктор по-умолчанию, либо убрать рекурсивные вызовы из DestroyTree:

template <typename T>
void Tree<T>::DestroyTree(Node<T> *root)
{
  delete root;
}

root на неравенство 0 можно не проверять, т.к. "delete 0" разрешенная операция.

5
  • За что минус? Я неправильно написал?
    – dzhioev
    8 июн 2012 в 22:46
  • Точно, DestroyTree не нужна вообще, лучше delete head вместо него написать. Про деструктор Tree по умолчанию я не понял, он не вызовет delete head.
    – sercxjo
    9 июн 2012 в 6:06
  • Во-первых в ~Node никаих рекурсивных вызовов нет. Во-вторых, delete root удалит корень дерева, а все, что ниже, останется
    – carapuz
    9 июн 2012 в 6:20
  • 1
    @carapuz, delete left и delete right как раз вызывают ~Node, так что рекурсия есть
    – sercxjo
    9 июн 2012 в 7:15
  • Все. Понял теперь. Извиняюсь.
    – carapuz
    9 июн 2012 в 8:16

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.