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

Автор: mind abuse 16.05.2008 4:10

Суть проблемы такова: в приложенном файле есть здоровое красивое бинарное дерево с многими удобствами, включая рисование самого себя /*не помню, где скачал, авторство, кажется, то ли 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;

Покажите пожалуйста, как переделать её в удаление только листьев, не имеющих соседей.


Прикрепленные файлы
 tree.pas ( 11.08 килобайт ) Кол-во скачиваний: 309

Автор: 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;

    del_leafs(root^.left);
    del_leafs(root^.right);
  end;
end;

Автор: mind abuse 17.05.2008 14:44

Спасибо! Всё весьма наглядно работает /*хоть на проверку этого сломавшийся компьютер отдал лишь последнтие пять минут своей жизни*/

Автор: plaquenil side effects mayo clin 19.09.2021 6:50

Propecia Msd Kaufen

Автор: buy stromectol online no prescri 8.11.2021 23:51

Prix Cialis En France