Бинарные деревья
   
Бинарные деревья (основные понятия)  
Операции над бинарными деревьями  
Обход дерева Графическое представление бинарного дерева
Применение бинарных деревьев Нерекурсивная работа с бинарным деревом


Бинарные деревья (основные понятия)

Определение:

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


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

Узел дерева, не имеющий потомков, называется листом.

Схематичное изображение бинарного дерева:
Бинарное дерево

Бинарное дерево может представлять собой пустое множество, и может выродиться в список. Вырожденное бинарное дерево:
Вырожденное бинарное дерево


Операции над бинарными деревьями

Бинарное дерево должно реализовывать следующие операции:
  1. Инициализация бинарного дерева:
    текущий указатель устанавливается неопределенным (или нулевым, nil), а количество узлов нулевым.

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

  3. Получение значения текущего элемента

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

  5. Удаление узла из дерева

  6. Уничтожение бинарного дерева


Рассмотрим эти операции более подробно:
  1. Структура для создания корня и узлов дерева имеет вид:
    type
    	T = Integer;	{ скрываем зависимость от конкретного типа данных }
    
    	TTree = ^TNode;
    	TNode = record
    		value: T;
    		Left, Right: TTree;
    	end;
    Здесь поля Left и Right - это указатели на потомков данного узла, а поле value предназначено для хранения информации.

  2. При создании дерева вызывается рекурсивная процедура следующего вида:
    procedure Insert(var Root: TTree; X: T);
    
    	{ Дополнительная процедура, создающая и инициализирующая новый узел }
    	procedure CreateNode(var p: TTree; n: T);
    	begin
    		New(p);
    		p^.value := n;
    		p^.Left := nil;
    		p^.Right := nil
    	end;
    	
    begin
    	if Root = nil Then CreateNode(Root, X) { создаем новый узел дерева }
    	else 
    		with Root^ do begin
    			if value < X then Insert(Right, X)
    			else
    				if value > X Then Insert(Left, X)
    				else 
    				{ Действия, производимые в случае повторного
    				внесения элементов в дерево}
    		end;
    end;
    Эта процедура добавляет элемент X к дереву, учитывая величину X. При этом создается новый узел дерева.

  3. Получить значение текущего элемента можно так:
    function GetNode(Root: TTree): T;
    begin
    	if Root = nil then WriteLn('Дерево - пусто!')
    	else
    		GetNode:=Root^.value
    end;
  4. Поиск заданного элемента (функция возвращает адрес узла с найденным элементом; если элемент в дереве не найден, возвращается nil):
    function Find(Root: TTree; X: T): TTree;
    begin
    	if Root = nil then Find := nil
    	else
    		if X = Root^.value then Find := Root
    		else
    			if X < Root^.value then Find := Find(Root^.Left, X)
    			else Find := Find(Root^.Right, X);
    end;
  5. Удаление узла бинарного дерева.

    Это немного более сложная операция, чем поиск заданного элемента. Сначала необходимо найти элемент, подлежащий удалению. Если этот элемент - лист, он может быть просто удален. Если же он является внутренним узлом (имеет потомков), то просто так удалить его не получится - будут разрушены внутренние связи в дереве.

    Поступаем так:

    Для реализации процедуры Remove желательно иметь функцию DeleteMin, которая будет удалять наименьший элемент непустого дерева Root, и возвращать значение удаленного элемента:
    function DeleteMin(var Root: TTree): T;
    var WasRoot: TTree;
    begin
    
    	if Root^.Left = nil then begin
    		DeleteMin := Root^.value;	{ Результат функции }
    		WasRoot := Root;		{ Запоминаем узел для последующего удаления }
    		Root := Root^.Right;		{ продвигаемся дальше }
    		Dispose(WasRoot);		{ удаляем бывший корень }
    	end
    	else { узел Root имеет левого "сына" }
    		DeleteMin := DeleteMin(Root^.Left);
    	
    end;
    Теперь процедура Remove может быть реализована так:
    procedure Remove(var Root: TTree; X: T);
    var WasNext: TTree;
    begin
    	if Root <> nil then
    		if X < Root^.value then Remove(Root^.Left, X)
    		else 
    			if X > Root^.value then Remove(Root^.Right, X)
    			else 
    				if (Root^.Left = nil) and (Root^.Right = nil) then begin
    					{ Нет "сыновей", удаляем узел, на который указывает Root }
    					Dispose(Root); 
    					Root := nil
    				end
    				else 
    					if Root^.Left = nil then begin
    						WasNext := Root^.Right;
    						Dispose(Root);
    						Root := WasNext;
    					end
    					else
    						if Root^.Right = nil then begin
    							WasNext := Root^.Left;
    							Dispose(Root);
    							Root := WasNext;
    						end
    						else { у удаляемого элемента есть оба "сына" }
    							Root^.value := DeleteMin(Root^.Right);
    end;
  6. Уничтожение бинарного дерева.
    Procedure Delete(T: TTree);
    Begin
      If T = nil Then Exit;
    
      Delete(T^.Right);
      Delete(T^.Left);
      Dispose(T)
    End;


Обход дерева

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

Рекурсивные алгоритмы прохождения бинарного дерева по каждому из перечисленных способов включают 3 одинаковых процедуры, где нужно пройти корень поддерева, левое поддерево текущего корня и правое поддерево текущего корня. Направление обхода однозначно определяет последовательность выполнения указанных процедур. Последовательность их рекурсивного вызова для каждого способа прохождения перечислена в следующей таблице.
Таблица рекурсивных алгоритмов прохождения бинарного дерева
--------------------------------------------------------------------------------
                           Порядок прохождения
--------------------------------------------------------------------------------
        Прямой          |     Симметричный      |       Концевой
--------------------------------------------------------------------------------
1. Корень поддерева     |1. Левое поддерево     |1. Левое поддерево
2. Левое поддерево      |2. Корень поддерева    |2. Правое поддерево
3. Правое поддерево     |3. Правое поддерево    |3. Корень поддерева
--------------------------------------------------------------------------------
  1. Прямой порядок прохождения означает обход в направлении сверху-вниз, когда после посещения очередного разветвления продолжается прохождение вглубь дерева, пока не пройдены все потомки достигнутого узла. По этой причине прямой порядок прохождения часто называют нисходящим, или прохождением в глубину.

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

    Уступы в ступенчатом списке, представляющем любую иерархическую структуру, также располагаются в прямом порядке. В генеалогических терминах прямой порядок прохождения дерева отражает династический порядок престолонаследования, когда титул передается старшему потомку.

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

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


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


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

Это реализуется вот такой процедурой:
procedure PrintByLevel(level: integer;
          var items: array of TTree; count: integer);
var i, new_count: integer;
begin
  if count <> 0 then begin

    writeln('level = ', level);
    new_count := 0;
    for i := 0 to pred(count) do begin
      write(items[i]^.value:4);
      if items[i]^.left <> nil then begin
        inc(new_count); items[count + new_count - 1] := items[i]^.left;
      end;
      if items[i]^.right <> nil then begin
        inc(new_count); items[count + new_count - 1] := items[i]^.right;
      end;
    end;
    writeln;
    move(items[count], items[0], new_count*sizeof(TTree));
    PrintByLevel(level + 1, items, new_count);

  end;
end;
Вызывать процедуру надо вот так:
var
  arr: array[0 .. pred(size)] of TTree; { <--- Здесь должно быть достаточно места для хранения }

begin
  { Заполнение дерева }
  ...
  arr[0] := root;
  PrintByLevel(0, arr, 1);
  ...
end.


Графическое представление бинарного дерева

Для отрисовки бинарного дерева в графическом режиме можно использовать процедуру PrintTreeGraph.
Примечание: приведенная процедура работает с деревьями, состоящими из символов (T = Char) или строк (T = String). Для того, чтобы она работала с другими типами, необходимо изменить функцию
Function Convert(X: T): String;
так, чтобы она преобразовывала необходимый тип к строке...
pgt.pas


Применение бинарных деревьев

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

Присоединенный модуль содержит основные функции для работы с бинарными деревьями.
treeunit.pas

Кроме основных функций в модуле содержится процедура подсчета числа "листьев" - узлов, не содержащих потомков (количество листьев возвращается в переменной k):
Procedure LeafsCount(T: TTree; Var k: Integer);
Процедуры обхода:
procedure PrintDown(level: integer; T: TTree);	{ Прямой порядок прохождения }
procedure PrintLex(level: integer; T: TTree);	{ Симметричный порядок прохождения }
procedure PrintUp(level: integer; T: TTree);	{ Концевой порядок прохождения }
Пример программы, использующей реализацию бинарного дерева:
uses TreeUnit;
const
	size = 10;
	iV: array[1 .. size] of Integer = (
		1, 4, 8, 2, 7, 4, 3, 8, 9, 3
	);
	
var
	i: Integer;
	myTree, wasfound: TTree;
	
begin
	myTree := nil;
	for i := 1 to size do begin
		Insert(myTree, iv[i]);
		PrintDown(0, myTree); WriteLn
	end;
	
	wasFound := Find(myTree, 7);
	if wasFound <> nil then
		WriteLn('x = ', GetNode(wasFound));
	
	Remove(myTree, 7);
	PrintDown(0, myTree);
end.


Нерекурсивная работа с бинарным деревом

Для итеративного добавления элемента к бинарному дереву может применяться следующая процедура:
Procedure AddIter(Var root: TTree; X: TType);

  { Функция, создающая новый лист дерева с заданным значением Data }
  Function CreateNode(n: TType): TTree;
  var p: TTree;
  Begin
    New(p);
    p^.Data := n;
    p^.Left := nil; p^.Right := nil;
    CreateNode := p;
  End;

var
  parent, pwalk: TTree;

Begin

  {
    Если корень дерева - нулевой (только начали заполнять дерево, например),
    то создаем новый элемент и запоминаем его, как корень
  }
  if root = nil then root := CreateNode(X)
  else begin

    { Если дерево уже не пустое - тогда начинаем "прогулку" по нему... }

    pWalk := root; { "гулять" начнем с корня }
    while pWalk <> nil do begin { пока не добрались до пустого указателя - делаем следующее }

      { запоминаем текущий элемент, в качестве "родителя" его потомка }
      parent := pWalk;

      {
        переходим в левую или правую ветвь в зависимости от соотношения величин
        нового элемента и "текущего", которым мы "гуляем" по дереву
      }
      if X < pWalk^.data then pWalk := pWalk^.left
      else pWalk := pWalk^.right

    end;

    {
      Если мы здесь - значит, добрались до пустого указателя...
      Вот теперь делаем то, для чего запоминали родителя текущего элемента:
      опять же в зависимости от того, больше или меньше добавляемое значение,
      чем значение "родителя", создаем новый элемент и запоминаем его в левой,
      или правой ветке...
    }

    if X < parent^.data then parent^.left := CreateNode(X)
    else parent^.right := CreateNode(X);

  end;

End;