В этом случае тоже используется несколько одномерных массивов, определяющих для каждой вершины левого и правого потомков предка и информацию, приписанную этой вершине.
Const Maxnodes=100; {максимальное число вершин}
Type TREE=record
Data:array[1..maxnodes] of info_type;
Parent:array[1..maxnodes] of integer;
Left:array[1..maxnodes] of integer;
Right: array[1..maxnodes] of integer;
Root:integer; {корень}
Node:integer; {текущее число вершин дерева}
Такое представление дерева поддерживает все указанные операторы, которое не изменяет структуры дерева, а так же позволяет достаточно просто добавлять новые вершины.
Function PARENT(i:integer;T:TREE);
Begin
If (i<1) or (i>T.node) then ERROR (“такой вершины не существует”)
Else PARENT:= T.parent[i];
End;
Рассмотрим оператор вставки левого потомка вершины i.
Procedure CREATE_L (i:integer; var T:TREE);
Begin
If (i<1) or (i>T.node) then ERROR (“такой вершины не существует”)
Else
If T.node=maxnodes then ERRROR (“вставка невозможна”)
Else
Begin
T.node:=T.node+1; T.parent[T.node]:=I;
T.left[T.node]:=0; T.right[T.node]:=0;
If T.left[i]<>0 then
Begin
T.left[T.node]:=T.left[i]; T.parent[T.left[i]]:=T.node;
End;
Left[i]:=T.node;
End;
Выполнение операций удаления вершины связано с необходимостью изменения нумерации оставшихся вершин дерева, что приводит к необходимости перезаписи всех массивов. В зависимости от решений задачи узловое представление можно упростить путем исключения части массивов. Например, если дерево всегда просматривается от корня к листьям, то не требуется массив предков. И наоборот, если дерево просматривается от листьев к корню, то можно не использовать массивы левых и правых потомков.
|
Главная
Каталог файлов
