Как удалить дерево, созданное динамическl

[Константин]

Здравствуйте всем!
Помогите пожалуйста!
Сам я с вопросом разобраться не сумел, ничего конкретного найти не смог . программированием занимаюсь не очень давно.
Мне надо организовать данные в веде дерева, новые узлы в него я добавляю динамически. я начал писать класс на подобие этого:
class AAA
{
int data;
AAA *prev,*left,*right;
AddLeft(..);
AddRight(..);
..
};
теперь я пишу AAA *p=new AAA; (это корень дерева), потом добавляю левое и правое поддеревья и тд. а в конце я хочу написать delete(p); и что бы все это дерево удалилось.
теперь проблема: я не догоняю как (конкретно) это сделать. ясно что удалять дерево надо рекурсивно. Помогите пожалуйста прегрузить delete, или быть может надо изначально подругому все делать (?) и еще сделать деструктор к этому слассу.
Спасибо!

[Джон]

Эммм...

Шаг 1
сделай ф-ю, которая бы получала в качестве параметра узел (node) и удаляла в цикле всех детей этого узла (если таковые имеются)

потом сделаем шаг 2

[Вад]

В принципе, как понимаю, тут дерево бинарное - даже цикла не надо Или не бинарное, left-right - это только 1й и последний из детей?

[Константин]

с этим проблем возникнуть вроде не должно.
вот как я понимаю ситуацию: эта функция будет использовать delete(), и она же будет находиться внутри перегруженного в моем классе delete()? но разве это не будет зацикливанием, или всмысле бесконечной рекурсией? или я вообще запутался? что же во 2-м шаге?

я могу сделать что б дерево удалялось так напр: p->mydelete(); но хотелосьбы именно delete(p);

[npak]

Код:

AAA::~AAA () {
  if (left) delete(left);
  if (right) delete(right);
}

В этом примере есть одна проблема - если вы построили дерево некорректно (например, зациклили), то delete впадет в бесконечный цикл. Это можно обойти так:

Код:

AAA::~AAA () {
  if (left) { AAA* tmp = left; left = 0; delete(tmp); }
  if (right) { AAA* tmp = right; right = 0; delete(tmp); }
}

Даже если в графе есть циклы, присваивания left = 0 и right = 0 их разорвут.

[Константин]

2npak: за деструктор благодарю! теперь осталось разобраться с перегрузкой delete()
меня только что посетили 3 мысли: 1) деструктор достаточно легкий, я мог бы и сам до него додуматься, в следующий раз так и поступлю. еще раз спасибо!
2)зачем мне деструктор, ведь все созданное динамически лучше удалять руками?
3)деструктор лишним никогда не бывает, для общности он должен быть, и пусть будет.
Спс еще раз!
2Вад: да, дерево двоичное
2Джон: вот что у меня получилось с функцией:

Код:

deltree(AAA *p)
{if( !p ) return;
deltree(p->left);
if( !p->left) delete(p->left);
deltree(p->right);
if( !p->right) delete(p->right);
}

смею надеяться, что работать она будет правильно

[Алексей++]

зачем мне деструктор, ведь все созданное динамически лучше удалять руками

если  указатель на выделенную память - мембер класса (так или иначе, как например лист дерева - прямо не мембер, но по корню его всё же можно найти) то в деструкторе обязательно надо убедиться и подчистить. Оно, конечно, можно и раньше это сделать в классе, но это не всегда удобно или тупо забудешь это сделать, а деструктор завсегда на стрёме

[Константин]

Так а что мне всетаки делать с delete()? 

[Джон]

А нафига она тебе нужна? Ты же деструктор сделал. Практически я от тебя ожидал ф-ю, тело которой приведено в коде деструктора от npak. А ты сразу с рекурсивным вызовом сделал. Но тебе и делать-то больше ничего не надо.
Рекурсия будет обеспечена в деструкторе. Поменяй только delete(tmp); на delete tmp; и всё.

И в основной программе:


AAA *p=new AAA;

// заполнение дерева

// удаление в нужный момент

delete p;

зы Ещё раз, на тот случай, если ты этого не видишь. Ты начинаешь удалять root дерева - в деструкторе будут удалены его дети (в твоём случае их 2, в общем их может быть больше), те будут вызваны их деструкторы, они в свою очередь удалют своих детей, те своих и тд. Вот и всё. А откуда ты сей несуразный тезис взял

2)зачем мне деструктор, ведь все созданное динамически лучше удалять руками?

ума не приложу. Автоматически деструктор удалит только сам объект, поэтому ты переписываешь его и дополняешь, что и называется работой ручками.

[Константин]

теперь кажись понял Всем Спасибо

[Константин]

Как и конструкторы, деструкторы могут вызываться явно (при помощи ​оператора С++ delete) или неявно - при выходе объекта из области ​действия

вот какой фразы мне не хватало для понимания картины происходящего. я, тормоз, думал, что delete - это delete, а деструктор - это деструктор. извините

[Джон]

Ааа те надо было ещё так написать, для пущей наглядности:


{

AAA p;
// заполнение дерева
}

// здесь будет вызван деструктор и всё дерево будет удалено.

[Антон (LogRus)]

я бы детей в умные указатели положил и на деструктор бы забил.

[Алексей++]

а ещё есть вариант: под дерево выделять память одним блоком (а в случае нехватки - перераспределить заново, скопировать уже накопленные данные)
Тогда: удаление делается одним delete [] ...

[RXL]

Алексей1153++, чтобы не перераспределять заново (с копированием данных) можно сделать двухуровневую модель блочного выделения памяти: использовать множество блоков, выделяемых по необходимости; создать каталог (массив) указателей на эти блоки (M указателей); каждый блок содержит N элементов; каждый элемент содержит два индекса: номер блока в каталоге и номер элемента в блоке.

[Алексей++]

Ром, тогда смысл ? Возвращаемся к куче указателей, заместо одного. А память под дерево можно выделять шагами по, скажем 4 метра (зависит от характера данных), это будет не так часто происходить. А ведь в момент начала работы ещё можно прикинуть примерный максимальный размер - тогда пересоздания вообще можно убежать )
А удаляется опять же одним махом

[RXL]

Леш, не к указателям - к индексам.

pointer = catalog[catalog_idx] + sizeof(element_t) * block_idx;

P.S.: по 4 МБ... Расточителен ты. Сразу видно - программишь для десктопов, а не для серверов.

[Алексей++]

ну я , во первых, для примера Говорюже - от задачи надо смотреть.

[lapulya]

Алексей1153++,
это

а ещё есть вариант: под дерево выделять память одним блоком (а в случае нехватки - перераспределить заново, скопировать уже накопленные данные)
Тогда: удаление делается одним delete [] ... Улыбаюсь

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

Кстати пушистый если твое предложение (то что я процитировал) вынести в функцию new для данного класса (а можно, если нужно, то и по-выше) получится как раз та самая оптимизация (опускаем замечание RXL с которым я кстати полностью согласен... это я про расточительство... но не важно, поскольку затевалась именно оптимизация) работы с памятью о которой мы как-то с тобой разговаривали, и ты помнится с пеной у рта доказывал что это типа не надо никому )))), а тут сам предложил...

[lapulya]

Джон,

Поменяй только delete(tmp); на delete tmp; и всё

лучше писать так delete(tmp);, почему - не помню, но так говорил или сам Страуструп или автор Effective stl, короче кто-то достаточно мной уважаемый (повторю я не помню его аргументацию, но автор настаивал на таком написании)

[Джон]

"Маразм крепчал" (с)

[lapulya]

Джон, если не веришь, могу и поискать...

[RXL]

Джон, подробнее, пожалуйста...

lapulya, примеры из книг и жизни никогда не помешают.

[Алексей++]

lapulya,

если твое предложение  вынести в функцию new для данного класса

йа?? вынести Никогда в жизни не переписывал new Не требовалось ни разу

[lapulya]

Алексей1153++,
new как правило переписывается для оптимизации по скорости реже для дефрагментации, ты предлагал сделать именно оптимизацию правда и по скорости и по удобству работы (это я про удаление). Видимо следуя твоему совету нужна была некая функция которая выделяла/перераспределяла память (ну там при добавлении/удалении узлов дерева) и вот если эту функцию назвать new, то мы и придем к тому от чего ты открещиваешься))), хотя предложил то сам!!! у меня пол интернета в свидетелях ))))

Ну а то что ни разу не требовалось... так это погоди... вся жизнь впереди, надейся и жди... ))))

[Алексей++]

lapulya, ты неправильно  меня понял Я не предлагал некую функцию (и Боже упаси меня трогать new ) ) я способ предлагал. А функцией это сделать или нет - решать автору

[Константин]

Разрешите задать еще один (уточняющий) вопрос (чтобы покончить (на время) с перегруженным delete'ом): когда я вызываю этот delete (напр. delete ( c )  ) то:
1)выполняется то, что написано в теле delete'а
2)освобождается память под указателем ( с ) ?
да?
И, значит, перегрузить delete так, чтобы он ничего не удалял не получится?

[Джон]

Константин, у тебя какое-то превратное понятие оператора вызова деструктора. Ты вобще-то теорию читаешь? И если да, то какую?

class A
{
public:
   A() {}

   ~A()
   {
      int i=3;
      // format c: и прочая чепуха
   }
};

   A *pA = new A();

   // delete pA; - здесь вызовется ~A();
   // или ты можешь написать явно:
        pA->~A();

   pA = NULL;

[Константин]

не, как вызывать деструктор я в курсе, я хотел уточнить что происходит конкретно при этом.
PS пжлста, не надо сравнивать меня с людьми, которые пишут сюда для того чтобы курсовую сдать или еще чего там, я хочу научиться прогать на С++, делаю это не потому что меня кто-то где-то заставляет, я делаю это для собственного удовольствия и полностью добровольно. Я читал кучу всякого, и вообще по алгоритмам, и конкретно про Си. К сожалению примеров прегрузки операторов там немного, delete'а вообще не встречал. как использовать различные средства языка там написано, но что конкретно стоит за каждым из этих средств - нет. это я и пытаюсь сейчас понять, и надеюсь на вашу помощь.
Если посоветуете чего еще почитать - не откажусь.

[Алексей++]

Константин, деструктор просто вызывается (гарантированно для автоматически созданных объектов или перед освобождением памяти после вызова delete для объектов, созданных через new). В деструкторе нужно проделать операции, необходимые для "чистки", например, а можно и ничего не делать