Структуры данных. Деревья - 8 стр.

UptoLike

Составители:

Рубрика:

Реализация таких рекурсивных структур, как двоичные деревья, приводит

к использованию ссылок (указателей).

Ссылки на пустые деревья будут обозначаться

nil.

Из определения двоичных деревьев следует естественный способ их опи-

сания ( и представления в компьютере ) : для этого достаточно иметь две связи L

и R в каждом узле и переменную связи T, которая является указателем на это де-

рево. Если дерево пусто, то T =

nil ; в противном случае T - адрес корня этого

дерева, а L и R - указатели соответственно на левое и правое поддеревья этого

корня.

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

или несколькими информационными полями и двумя полями – указателями. Ес-

ли Elem - тип информационной части узлов дерева, то компоненты дерева ( узел

и ссылка на узел ) имеют такие типы:

type Tree = ^Node; { указатель на узел }

Node = record { узел дерева }

inf : Elem;

L, R : Tree

end;

Таким образом, дерево на рисунке

4 б) можно представить так, как на

рисунке 5.