Курсовая работа: Ссылочные типы. Динамические переменные

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

Данную структуру целесообразно описать следующим образом:

type

TypeOfElem= {};

Assoc= ^ElemOfTree;

ElemOfTree= record

Elem: TypeOfElem;

Left, Right: Pointer

end;

4.1 Поискэлементавдереве

function FoundInTree( Elem: TypeOfElem; var Tree, Result: Pointer ): Boolean;

var

ServiceVar: Assoc;

b: Boolean;

begin

b:= False;

ServiceVar:= Tree;

if Tree <> nil then

repeat

if ServiceVar^.Elem= Elem then b:= True

else

if Elem < ServiceVar^.Elem then ServiceVar:= ServiceVar^.Left

else ServiceVar:= ServiceVar^.Right

until b or ( ServiceVar= nil );

FoundInTree:= b;

Result:= ServiceVar

end;

4.2 Включение элемента в дерево

Включение элемента в дерево реализуется путем во-первых, поиска вершины √ предка нового элемента, во-вторых, непосредственным включением элемента в дерево по найденной позиции. Опишем процедуру поиска предка для нового элемента.