Деревья

Определение дерева

1. Дерево с типом узлов T - это либо:
   пустое дерево; либо
2. некоторая вершина типа T (корень) с конечным числом связанных с ней отдельных деревьев с типом узлов T, называемых поддеревьями.

Данное определение является рекурсивным. Рекурсия используется в большом числе алгоритмов работы с деревьями.

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

Изображение структуры деревьев

1. Вложенные множества.

   

   Здесь A - корневая вершина; B - корень первого поддерева для A; C - корень второго поддерева для A.

2. Вложенные скобки.

   ( A ( B (D (I), E (J, K, L) ), C (F (O), G (M, N), H (P) ) ) )

3. Таблица
   

   A
   B				C
   D	E			F	G		H
   I	J	K	L	O	M	N	P

4. Отступы
   

   Уровни
   0	1	2	3
   A
   	B
   		D
   			I
   		E
   			J
   			K
   			L
   	C
   		F
   			O
   		G
   			M
   			N
   		H
   			P

5. Граф

   

   Дерево - связный граф без циклов. Изображается корнем сверху.

Некоторые определения

Упорядоченное дерево - это дерево, к которого ребра (ветви), исходящие из каждой вершины, упорядочены. Поэтому следующие два упорядоченных дерева - разные, отличные друг от друга объекты:

Непосредственный потомок вершины X - вершина Y, находящаяся непосредственно ниже X и связанная с ним. При этом вершина X является непосредственным предком Y (X родительская вершина для Y). Например, в следующем дереве вершины J, K, L являются потомками E, а E для них - предок. В свою очередь, E является потомком B, а B для нее - предок.

Если вершина не имеет потомков, то ее называют терминальной вершиной или листом. Нетерминальные вершины (имеющие потомков) называются внутренними.

Уровень вершины (узла) дерева - удаленность вершины от корня. Уровень корня равен нулю.

Максимальный уровень вершин в дереве называется высотой или глубиной дерева.

Пример:

Высота дерева равна 3; листья: B, D, F, G; внутренние вершины: A, C, E.

Число потомков вершины называется степенью вершины. Например, в следующем дереве

степень E равна 3, степень B - 2, степень D - 1, степени I, J, K, L - 0 (листья всегда имеют степень 0).

Линейный список можно рассматривать как дерево со степенью узлов не выше 1. Например, список A - B - C - D - E можно представить в виде следующих вырожденных деревьев:

A
 \
   B
     \
       C
         \
           D
             \
               E

                     A
                   /
                  B
                /
              C
            /
          D
        /
      E

          A
            \
              B
            /
         C
           \
             D
           /
         E

Двоичные (бинарные) деревья

Двоичное (бинарное) дерево - это упорядоченное дерево со степенью вершин не вы-ше 2. У каждой вершины такого дерева есть не более 2 поддеревьев, называемых левым и правым поддеревьями. Примеры:

1.  

   

2. Дерево выражения (a+b/c)*(d-e*f):

   

3. Генеалогическое дерево, где у каждого человека есть отец и мать.

Везде далее будем под термином <дерево> подразумевать <упорядоченное двоичное дерево>.

type ptr = ^node; 
   
node = record 
	info : char;
	llink, rlink : ptr
end;

Поле info содержит информацию, хранящуюся в вершине, а поля llink и rlink являются указателями на левое и правое поддерево соответственно. Если у вершины нет какого-либо из поддеревьев, то соответствующий ему указатель равен nil.

Тогда дерево выражения (a+b/c)*(d-e*f) в памяти будет храниться следующим образом:

(root - указатель на корень дерева).

Алгоритм построения дерева из n вершин с равномерным их размещением

При заданном числе вершин n минимальная высота дерева будет достигнута, если на всех уровнях, кроме последнего, помещается максимально возможное число вершин (на уровне k можно разместить до 2k вершин). Такое дерево называется идеально сбалансированным.

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

1. Взять одну вершину в качестве корня.
2. Построить таким же способом левое поддерево из nl = n div 2 вершин.
3. Построить таким же способом правое поддерево из nr = n - nl - 1 вершин.

Функция Tree строит идеально сбалансированное дерево из n вершин и возвращает ука-затель на корень дерева:

function Tree( n : integer ) : ptr;
var 	newnode : ptr;
	nl, nr : integer;
	x : char;
begin
	if n <= 0 then Tree := nil
	else begin
		nl := n div 2;
		nr := n - nl - 1;
		read(x);
		new(newnode);
		newnode^.info := x;
	newnode^.llink := Tree(nl);
	newnode^.rlink := Tree(nr);
	Tree := newnode;
	end;
end;

Использование:

var	root : ptr;
	n : integer;
begin
	writeln('Введите число узлов');
	read(n);
	root := Tree(n);
	:
end.

Пример работы для 7 узлов A, B, C, D, E, F, G (нарисовать структуру вложенных рекурсивных вызовов):

Печать дерева на экране начиная со строки номер h

uses crt;
procedure PrintTree( p : ptr; h : integer );
begin

	if p^.llink <> nil then PrintTree(p^.llink, h+1);

	gotoxy(wherex, h);
	write(p^.info);
	if p^.rlink <> nil then PrintTree(p^.rlink, h+1);
end;

(функция wherex из модуля crt возвращает текущую координату x курсора, а процедура gotoxy устанавливает курсор в заданную позицию на экране).

(нарисовать структуру вложенных рекурсивных вызовов для дерева из 7 узлов)

Литература

1. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. - М.: Мир, 1989.
2. Кнут Д. Искусство программирования для ЭВМ: Т.1: Основные алгоритмы: Пер. с англ. - М.: Мир, 1976.

Copyright c2000-2002 Михаил Марковский
Перевод в HTML Александр Бессонов