While notEOF(F) do

Begin

Var

Begin

Var

Type

Const

Uses

Type

Пример.

Type

Пример.

Type

Const

Пример.

Сильно ветвящиеся деревья

 

Сильноветвящимися называются деревья, каждый из узлов которых может иметь более двух потомков. Максимальное количество потомков у одного узла называется степенью дерева. В частном случае, двоичное дерево есть дерево степени 2.

 

Следует различать несколько подвидов сильноветвящихся деревьев.

 


1. Дерево, каждый узел которого имеет не более чем N потомков (N – постоянное для данного дерева число).

N = 8;

pMyTreeNode = ^MyTreeNode;

MyTreeNode = record

iKey: integer; // Ключевое поле

nKey: integer; // Количество посещений данного узла

mpChild: array[1 .. N]ofpMyTreeNode;

npChild: integer; // Текущее количество потомков, <= N

end;

 

Недостаток такой структуры состоит в том, что для некоторых узлов число N намного больше количества реальных потомков (память под узел типа
MyTreeNode расходуется неэкономно), тогда как для других узлов число N недостаточно для указания всех требуемых потомков.

 


2. Дерево, каждый узел которого может иметь произвольное (неограниченное) количество потомков. Ссылки на них хранятся в элементах динамического массива.

pMyTreeNode = ^MyTreeNode;

MyTreeNode = record

iKey: integer;

nKey: integer;

mpChild: array ofpMyTreeNode;

end;

 

В записи MyTreeNode массив mpChild представлен лишь указателем на то место оперативной памяти, где располагаются элементы динамического массива. «Разбирательство» с увеличением или уменьшением числа элементов динамического массива ложится на операционную систему. При «переделке» дерева на хранение на дисках программист вынужден сам решать, где ему располагать элементы массива mpChild, что не всегда легко. Разговор об этом позже будет продолжен.

3. Дерево, каждый узел которого может иметь произвольное (неограниченное) количество потомков. Для узлов такого дерева уместно ввести новое отношение «старший брат» – «младший брат». Все потомки узла-предка являются «братьями», с узла-предка имеется ссылка только на одного из них – на «старшего брата». «Братья» (от старшего к младшему) выстроены в виде линейного списка.

pMyTreeNode = ^MyTreeNode;

MyTreeNode = record

iKey: integer;

pChild, pBrother: pMyTreeNode;

end;

 

 

4. Дерево, каждый узел которого ссылается на своих потомков с помощью вспомогательного дерева. Применяется для деревьев очень большой степени, когда даже отношение «предок-потомок» приходится оптимизировать по скорости доступа.


programProject1;

 

{$APPTYPE CONSOLE}

 

{$DEFINE StaticArrayOfChildren} // Первый подвид
// {$DEFINE DynamicArrayOfChildren } // Второй подвид
// {$DEFINE ListOfBrothers} // Третий подвид

// Следует «включать» один и только один из этих трёх режимов

 

SysUtils;

 

{$IFDEF StaticArrayOfChildren }

N = 8;

{$ENDIF}

 

pMyTreeNode = ^MyTreeNode;

 

MyTreeNode = record// Узел дерева

iKey: integer;

nKey: integer;

 

{$IFDEF StaticArrayOfChildren }

mpChild: array[1 .. N]ofpMyTreeNode;

{$ENDIF}

{$IFDEF DynamicArrayOfChildren }

mpChild: array ofpMyTreeNode;

{$ENDIF}

{$IFDEF ListOfBrothers}

pChild, pNext: pMyTreeNode;

{$ENDIF}

end;

 

 

MyTableType = record// элемент таблицы посещаемости ключей дерева

iKey: integer;

nKey: integer;

end;

 

MyProcType = procedure(varpThis: pMyTreeNode);

// Процедурный тип для процедур, работающих с посещаемыми узлами дерева

pRoot: pMyTreeNode;

mTable: array ofMyTableType;

iKeySought: integer;

nAux: integer;

procedureAway(i: integer);

// Процедура для «аварийного» завершения программы в нештатных ситуациях

WriteLN(‘Выброс – ‘, i);

ReadLN;

Halt;

end;

 

procedureReadTree;

F: TextFile;

S: string;

iDepth, iDepthPrev, i: integer;

pCurr,pParent,pAux: pMyTreeNode;

mPath: array ofpMyTreeNode;

 


ifpRoot <> nil thenexit;

 

Finalize(mPath);

 

AssignFile(F, 'Tree1.TXT');

Reset(F);

 

iDepthPrev := -1;