Для деревьев произвольного вида узловое представление использовать затруднительно, так как вершина может иметь произвольное число потомков. В таких случаях обычно используют представление деревьев на основе списков потомков, которые определяются для каждой вершины дерева. Такие списки могут представляться любым способом, но чаще используются связанные списки.
Программное описание структуры можно представить следующим образом:
Type
LIST={тип лист, описание списков}
Position={определение позиции в списке}
TREE=record
Header:array[1..maxnodes] of LIST;
DATA:array[1..maxnodes] of info_type;
Root:integer;
Node:integer; {текущее число вершин}
End;
В простейшем случае для реализации списков потомков можно использовать один единственный одномерный массив. Тогда описание абстрактного типа данных дерево (TREE) будет иметь следующий вид:
Type
TREE=record
Header:array[1..maxnodes] of integer;
DATA:array[1..maxnodes] of info_type;
nodes:array[1..maxnodes] of integer;
Root:integer;
Node:integer;
End;
Для такого представления нумерация вершин может быть совершенно произвольной.
Определение левого потомка, правого и предка.
function LEFT (i:integer; T:TREE):integer;
var R:integer;
begin
LEFT:=T.header[i];
End;
Function RIGHT (i:integer; T:TREE):integer;
Var R:integer;
Begin
R:=T.header[i];
If R=0 then RIGHT:=0 {лист}
Else
Repeat
RIGHT:=R; R:=T.nodes[RIGHT];
Until R:=0;
End;
Function PARENT (i:integer; T:TREE):integer;
Var P,j:integer;
Begin
PARENT:=0; {предок не найден}
For p:=1 to T.node do
Begin
j:=T.header[P];
while j<>0 do
if i=j then PARENT:=P
else j:=T.nodes[j];
end;
end;
end;
|
Главная
Каталог файлов
Главная
