Удаление листьев дерева Опции

[Account]

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

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

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

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

Сообщение отредактировано: Account - 13.10.2010 23:26

[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 пробела отступ, оригинал.

Сообщение отредактировано: TarasBer - 13.10.2010 23:34

[Account]

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

Сообщение отредактировано: Account - 14.10.2010 0:34

[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, попробовал вроде все норм работает, но все равно еще сам попробую, а то как то нет желания чужое брать. На крайний случай если все же у самого не выйдет. А тебе очередное СПАСИБО!

Сообщение отредактировано: Account - 14.10.2010 3:00

[Account]

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

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

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

Сообщение отредактировано: Account - 14.10.2010 15:56

[volvo]

если дерево состоит из одного корня, то оно удаляется.

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

Задание: Удалить все листья дерева.

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

[Account]

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

[мисс_граффити]

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

[Account]

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

[Account]

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