1.3.4. Деревья 1.3.4.1. Общие понятия

Дерево является одним из важных и интересных частных случаев графа, поэтому оно рассматривается отдельно от графов других видов. Деревом называется орграф, для которого:

1. существует узел, в который не входит ни одной дуги (корень);

2. в каждую вершину, кроме корня, входит одна дуга. Вершины дерева подразделяют на следующие три группы: – корень – вершина, в которую не входит ни одной дуги; – узлы – вершины, в которые входит одна дуга и выходит одна или

более дуг;

– листья – вершины, в которые входит одна дуга и не выходит ни одной дуги.

Все вершины, в которые входят дуги, исходящей из одной вершины, называются потомками этой вершины, а сама вершина – предком. Ко­рень не имеет предка, а листья не имеют потомков.

Выделяют уровни дерева. На первом уровне дерева может быть только одна вершина – корень, на втором – потомки корня, на третьем – по­томки потомков корня и т. д.

Поддеревом называется вершина со всеми ее потомками.

55

Высотой поддерева будем считать максимальную длину цепи y₁, …, y_n его вершин такую, что y_i+1 – потомок y_i для всех i. Высота пустого дерева равна нулю, высота дерева из одного корня – единице.

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

По величине степени дерева часто различают два типа деревьев:

– двоичные – степень дерева не более двух;

– сильноветвящиеся – степень дерева произвольная.

Дерево произвольной степени (сильноветвящееся дерево) можно реа-лизовывать как любой граф (см. 1.3.3.2). Однако, учитывая специфику де­рева как частного случая графа, можно рассмотреть отдельный способ реа­лизации – как динамическую структуру в виде списка (рис. 14). Списоч­ное представление деревьев произвольной степени основано на элемен­тах, соответствующих вершинам дерева. Каждый элемент имеет поле дан­ных и два поля указателей: указатель на начало списка потомков вершины и указатель на следующий элемент в списке потомков текущего уровня. При таком способе представления дерева обязательно следует сохранять указатель на вершину, являющуюся корнем дерева:

type PTree

^ATTree;

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

Динамическая реализация

Указатель на дерево

							d1
							_^
				'			—
							nil
			d2			d3		d4		d5
						nil		nil		_
						^		^		nil
					"^	*		*	^J
\	у
d6			d7			d8				d5
nil			nil			nil				nil
						nil				nil

56

Рис. 14. Дерево произвольной степени и его динамическая организация

TTree = record

Data: TypeElement; {поле данных}

Childs, Next: PTree; {указатели на потомков и на следующий} end;