Организация и функционирование компьютеров


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


Ее состав зависит от функций, которые она должна обеспечивать. По крайней мере, необходимо уметь перечислить вершины дерева в порядк взрастания. Для этого можно предложить следующую схему. Для каждой вершины будем задавать структурную информацию в виде двух указателей. Первый указатель ссылается на первого по порядку слугу данной вершины. Если вершина тупиковая и слуг не имеет, то указатель пусть равен значению Nil. Второй указатель ссылается на следующего по порядку слугу среди слуг хозяина данной вершины. Если данная вершина последняя в списке слуг своего хозяина, то указатель пусть также равен значению Nil. Система вторых указателей превращает дерево в совокупность линейных однонаправленных списков слуг некоторого хозяина. Первый указатель при вершине содержит ссылку на начало списка

type

    rec = record  <поля данных>  end;       {запись данных}

    ptree = ^tree;                                              {тип указателя на элемент списка }

    tree = record                                              {тип элемента списка}

                    data: rec;                                     {данные вершины дерева}

                    down: ptree                                 {ссылка на 1-го слугу данной вершины}

                    right: ptree                                  {ссылка на следующего слугу хозяина вершины}

                end;

var  root: ptree;                                              {ссылка на корневую вершину дерева}

Пусть теперь дерево описывается в форме совокупности динамических переменных, каждая из которых задает вершины дерева. Приведем пример процедуры, выводящей в файл данные всех вершин дерева в лексикографическом порядке.

procedure  write_tree (f: tpf);  {f - файловая переменная типа  tpf = file

of rec}

var  k: integer;

        path: array [1..20] of  tree;

begin

    k := 1;

    path [k] := root;    {Начальная вершина дерева - корневая}

    while  (k>0) and

(path[k]<>Nil) do

        begin




- Начало -  - Назад -  - Вперед -