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

Назовем корневую вершину вершиной первого уровня, ее сыновей – вершинами второго уровня, сыновей ее сыновей – вершинами третьего уровня и т.д. Максимальный уровень называется глубиной дерева. Далее, для каждой вершины перенумеруем дуги, выходящие из этой вершины. Можно ввести так называемый лексикографический порядок на множестве вершин дерева. Именно, для каждой пары вершин возьмем два пути, ведущие из корня в эти вершины. Тогда эти пути либо один продолжает другой, либо они расходятся с некоторой точки. В первом случае будем предполагать, что более длинный путь следует за более коротким. Во втором случае порядок определяется номерами первых несовпадающих дуг путей.

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

1.1.1

2.1.2 2.2.8 2.3.10 2.4.11

3.1.3 3.2.6 3.1.9 3.1.12 3.2.13 3.3.18

4.1.4 4.2.5 4.1.7 4.1.14 4.2.15 4.3.16 4.4.17

Тупиками являются вершины с номерами 4,5,7,9,10, 12,14,15,16,17,18.

Важным свойством дерева является свойство подобия, которое заключается в том, что множество всех потомков данного хозяина (сыновей, сыновей сыновей и т.д.) образуют дерево. Оно является поддеревом дерева с корнем в данной вершине. Такое поддерево иногда называют ветвью дерева. В частности, каждое дерево состоит из корня дерева и нескольких ветвей, корнями которых служат все вершины первого уровня дерева.

Деревом изображаются любые иерархические структуры, которые очень часто встречаются на практике. Например структура подразделений компании или структура административного деления регионов. Деревом является классификация видов животных или перечень номенклатуры изделий (и вообще, любая классификация). Иерархия объектов в реальной действительности приводит к иерархии описаний объектов в памяти компьютера.

Как и в случае списков, описание вершины дерева состоит из двух частей: содержательной информации (описания объекта) и структурной информации (положения объекта в дереве). В данный момент нас интересует структурная информация. Ее состав зависит от функций, которые она должна обеспечивать. По крайней мере, необходимо уметь перечислить вершины дерева в порядк взрастания. Для этого можно предложить следующую схему. Для каждой вершины будем задавать структурную информацию в виде двух указателей. Первый указатель ссылается на первого по порядку слугу данной вершины. Если вершина тупиковая и слуг не имеет, то указатель пусть равен значению 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}