Версия для печати темы

Автор: Account 14.10.2010 3:18

Есть задача. Имеется бинарное дерево. Информация в узлах не важна (могут быть цифры, могут быть буквы).
Задание: Удалить все листья дерева.

Допустим делаем обход

Procedure obhod(p:tree); 
Begin 
   if p<>nil then 
   begin 
      obhod(p^.left); 
      writeln(p^.inf); 
      obhod(p^.right); 
   end; 
end;

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

Автор: TarasBer 14.10.2010 3:33

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 14.10.2010 4:06

Это удаляет полностью дерево, по поводу пробелов не догнал?

Автор: volvo 14.10.2010 5:06

Сам-то как думаешь? Задание явно говорит:
Твой код последовательно удаляет все листья до получения пустого дерева.

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 14.10.2010 6:59

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

Автор: Account 14.10.2010 19:40

volvo единственное баг, если дерево состоит из одного корня, то оно удаляется. Пока выявил только это).

Подправил этот баг вызовом функции из главной программы вот с таким условием:

if not (( t^.llink=nil) and (t^.rlink=nil)) then dellist(t);

Автор: volvo 14.10.2010 20:10

Какой же это баг? Это правильное поведение: если в дереве только один корень - это лист. Где-то сказано, что корень не может быть листом? Нет. По определению лист - это узел, у которого нет потомков.

Вот я его и удаляю. Что не так? Если тебе нужно было оставлять корень независимо от того, есть ли потомки - надо было говорить сразу, я бы сделал по-другому.

Автор: Account 14.10.2010 20:11

volvo, ок. Значит не баг, но для себя подправил, чтоб если что препод не придирался)))

Автор: мисс_граффити 14.10.2010 20:16

я бы на месте препода наоборот придралась к "исправленному" поведению

Автор: Account 14.10.2010 20:20

мисс_граффити, посмотрим, придерется исправим обратно и все, деловто. По сути volvo прав на все 100%.

Автор: Account 14.10.2010 22:39

Всю ночь просидел но так своего алгоритма не придумал, видимо мозгов не хватает))))
Еще раз спасибо volvo.