Предыдущая страница реферата | 16  17  18  19  20  21  22  23  24  25  26 | Следующая страница реферата

{подсоединить новую вершину к дереву}

if Elem < Result^.Elem then Result^.Left:= Node

else Result^.Right:= Node

end

end;

Двоичное дерево можно рассматривать как рекурсивную структуру данных, состоящую из корневой записи, указывающей на левое и правое поддерево. Оба поддерева имеют такую же структуру: корень поддерева и правое и левое поддеревья. При этом, для представления дерева рекурсивной динамической структурой целесообразно модифицировать описание типа дерева, данное выше. А именно, удобнее изменить тип ссылок на левое и правое поддеревья с нетипизированного (Pointer) на типизированный:

type

TypeOfElem1= {};

Assoc1= ^ElemOfTree1;

ElemOfTree1= record

Elem: TypeOfElem1;

Left, Right: Assoc1

end;

Опишем процедуру вставки элемента рекурсивно.

procedure IncludeInTree2( NewElem: Assoc1; var SubTree: Assoc1 );

begin

if SubTree= nil then begin

SubTree:= NewElem;

NewElem^.Left:= nil;

NewElem^.Right:= nil;

end

else

if NewElem^.Elem < SubTree^.Elem then

IncludeInTree2( NewElem, SubTree^.Left )

else

IncludeInTree2( NewElem, SubTree^.Right )

end;

4.3 Удаление элемента дерева

Проблема реализации данной операции состоит в том, что в общем случае, в удаляемую вершину входит одна связь, а выходят две. Поэтому, необходимо найти подходящий элемент дерева, который можно было бы вставить на место удаляемого. Этот элемент является либо самым правым элементом левого поддерева (для достижения этого элемента необходимо перейти в следующую вершину по левой ветви, а затем, переходить в очередные вершины по правым ветвям до тех пор, пока очередная такая ссылка не будет равна nil), либо самый левый элемент правого поддерева (для достижения этого элемента необходимо перейти в следующую вершину по правой ветви, а затем, переходить в очередные вершины по левым ветвям до тех пор, пока очередная такая ссылка не будет равна nil). Процедура исключения элемента из двоичного дерева должна различать тои случая:

1. элемента с заданной информативной частью в дереве нет; 2. элемент с заданной информативной частью имеет не более одной ветви; 3. элемент с заданной информативной частью имеет две ветви.

procedure DeleteElemOfTree( var Tree: Assoc1; Elem: TypeOfElem1 );

var

ServiceVar1: Assoc1;

procedure Del( var ServiceVar2: Assoc1 );

begin

if ServiceVar2^.Right= nil then begin

ServiceVar1^.Elem:= ServiceVar2^.Elem;

ServiceVar1:= ServiceVar2;

ServiceVar2:=ServiceVar2^.Left

end

else Del( ServiceVar2^.Right )

end;

begin

{удаление элемента с информативным полем равным Elem из дерева Tree}

if Tree= nil then

{первый случай процедуры удаления}

writeln( 'Элемент не найден' )

else

{поиск элемента с заданным ключом}

if Elem < Tree^.Elem then DeleteElemOfTree( Tree^.Left, Elem )

Рекомендуем скачать другие рефераты по теме: источники реферат, ответы по алгебре.



Предыдущая страница реферата | 16  17  18  19  20  21  22  23  24  25  26 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки