Помощь - Поиск - Пользователи - Календарь
Полная версия: Удаление листьев дерева
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Account
Есть задача. Имеется бинарное дерево. Информация в узлах не важна (могут быть цифры, могут быть буквы).
Задание: Удалить все листья дерева.

Допустим делаем обход
Procedure obhod(p:tree); 
Begin
if p<>nil then
begin
obhod(p^.left);
writeln(p^.inf);
obhod(p^.right);
end;
end;

Пока не додумаюсь никак, как реализовать удаление листа и при этом не удалить предыдущий узел, который после удаления листа сам может стать листом? (Думаю если только сначала обойти, запомнить какие узлы являются листьями и потом уже повторно обойти и удалить их)
TarasBer

Procedure DelTree(var p:tree);
Begin
if p<>nil then begin
DelTree(p^.Left);
DelTree(p^.Right);
Dispose(p);
p := nil;
end;
end;


Катит?

гы, 3 пробела отступ, оригинал.
Account
Это удаляет полностью дерево, по поводу пробелов не догнал?
volvo
Цитата
Катит?
Сам-то как думаешь? Задание явно говорит:
Цитата
как реализовать удаление листа и при этом не удалить предыдущий узел, который после удаления листа сам может стать листом?
Твой код последовательно удаляет все листья до получения пустого дерева.

Account, вот чего я набросал:
function del_leaves(var p: ttree): boolean;
var
Lt, Rg: boolean;
begin
del_leaves := false;
if p = nil then exit;

del_leaves := true;
Rg := del_leaves(p^.right);
Lt := del_leaves(p^.left);

// только не надо умничать и вносить все вычисления вот в этот if,
// и избавляться от переменных Lt и Rg...
// Если я этого не сделал - значит, для этого были причины.
if not(Lt or Rg) then
begin
dispose(p);
p := nil;
end;
end;

Причин не работать не вижу, дерево создавать лениво, поэтому не проверял. Компиляцию вроде проходит.
Account
volvo, попробовал вроде все норм работает, но все равно еще сам попробую, а то как то нет желания чужое брать. На крайний случай если все же у самого не выйдет. А тебе очередное СПАСИБО! good.gif
Account
volvo единственное баг, если дерево состоит из одного корня, то оно удаляется. Пока выявил только это).

Подправил этот баг вызовом функции из главной программы вот с таким условием:
if not (( t^.llink=nil) and (t^.rlink=nil)) then dellist(t);
volvo
Цитата
если дерево состоит из одного корня, то оно удаляется.
Какой же это баг? Это правильное поведение: если в дереве только один корень - это лист. Где-то сказано, что корень не может быть листом? Нет. По определению лист - это узел, у которого нет потомков.
Цитата
Задание: Удалить все листья дерева.

Вот я его и удаляю. Что не так? Если тебе нужно было оставлять корень независимо от того, есть ли потомки - надо было говорить сразу, я бы сделал по-другому.
Account
volvo, ок. Значит не баг, но для себя подправил, чтоб если что препод не придирался)))
мисс_граффити
я бы на месте препода наоборот придралась к "исправленному" поведению
Account
мисс_граффити, посмотрим, придерется исправим обратно и все, деловто. По сути volvo прав на все 100%.
Account
Всю ночь просидел но так своего алгоритма не придумал, видимо мозгов не хватает))))
Еще раз спасибо volvo.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.