Суть проблемы такова: в приложенном файле есть здоровое красивое бинарное дерево с многими удобствами, включая рисование самого себя /*не помню, где скачал, авторство, кажется, то ли volvo, то ли другого пользователя*/ и в нём есть процедура удаления элемента:
procedure delelem(var root:PTree;info:byte); var temp:PTree; begin if (root<>NIL) then (* Если дерево не пустое, то *) begin if (info<root^.info) then (* Если удаляемый элемент меньше тек. узла, то *) delelem(root^.left,info) (* Удалить его из левого поддерева *) else (* Иначе *) if (info>root^.info) then (* Если удаляемый элемент больше тек. узла, то *) delelem(root^.right,info) (* Удалить его из правого поддерева *) else (* Иначе тек. узел - удаляемый элемент *) begin if (root^.left=NIL) and (root^.right=NIL) then (* Если тек. узел - лист, то *) begin dispose(root); (* Удалить его *) root:=NIL; (* Поставить на его место пустое дерево *) end else if (root^.left=NIL) and (root^.right<>NIL) then (* Если у тек.узла есть только правая ветвь *) begin temp:=root; (* Присоединить её вместо тек. узла *) root:=root^.right; dispose(temp); (* Удалить тек. узел *) end else if (root^.left<>NIL) and (root^.right=NIL) then (* Если у тек.узла есть только левая ветвь *) begin temp:=root; (* Присоединить её вместо тек. узла *) root:=root^.left; dispose(temp); (* Удалить тек. узел *) end else (* Иначе у узла есть обе ветви *) begin root^.info:=getmostright(root^.left); (* Вставить на место узла самый правый эл-т левого поддерева *) delelem(root^.left,root^.info); (* Удалить самый правый эл-т из левого поддерева *) end;
end; end; end;
Покажите пожалуйста, как переделать её в удаление только листьев, не имеющих соседей.
volvo
16.05.2008 4:24
Нет, это программа не моя, это демонстрационная программа по работе с деревьями из FAQ-а форума...
Можно уточнить, что значит,
Цитата
удаление только листьев, не имеющих соседей.
? Какие листья имеют соседей? Определение "соседства" можно привести?
mind abuse
16.05.2008 4:51
Я подразумеваю лист как узел, не имеющий потомков, соответственно, если от узла b отходят листья a и c, то мы их не трогаем, если только a - удаляем его.
volvo
16.05.2008 6:25
По-моему, нигде не ошибся, проверь:
procedure del_leafs(var root: ptree);
function is_leaf(p: ptree): boolean; begin is_leaf := (p <> nil) and (p^.right = nil) and (p^.left = nil); end;
begin if root <> nil then begin
if (root^.left = nil) then if is_leaf(root^.right) then begin dispose(root^.right); root^.right := nil; exit; end;
if (root^.right = nil) then if is_leaf(root^.left) then begin dispose(root^.left); root^.left := nil; exit; end;