Основные алгоритмы работы с деревьями, основанные на обходах

Подсчет числа узлов в бинарном дереве

Задача: подсчитать число узлов в бинарном дереве.

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

подсчет числа узлов в дереве

procedure count(p : ptr; var n : integer);
begin 
	if p<>nil then 
	begin	
		n := n+1; 
		count(p^.llink, n); 
		count(p^.rlink, n); 
	end;
end;

a-обход

procedure klp(p : ptr);
begin 
	if p <> nil then 
	begin 
		write(p^.info);
		klp(p^.llink); 
		klp(p^.rlink);
	end;
end;

Использование процедуры подсчета:

{ root указывает на корень дерева }
  k := 0;
  count(root, k);
  { k равно числу узлов в дереве }

(Пройти алгоритм по шагам на примере дерева:

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

function count(p:ptr) : integer;
begin
	if p=nil then count := 0
	else count := 1 + count(p^.llink) + count(p^.rlink);
end;
  

Подсчет числа узлов на заданном уровне

Задача: подсчитать число узлов в бинарном дереве на заданном уровне level.

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

procedure countlevel(p : ptr; level, current : integer; var n : integer);
{ p - указатель на узел дерева; level - заданный уровень дерева; 
current - номер текущего уровня; n - счетчик числа узлов }
begin
	if p<>nil then
  	begin
  		if current=level then n := n+1;
	  	countlevel(p^.llink, level, current+1, n);
  		countlevel(p^.rlink, level, current+1, n);
  	end;
end;

Использование процедуры подсчета:

{ root указывает на корень дерева, level равно заданному уровню }
k := 0;
countlevel(root, level, 0, k);
k равно числу узлов в дереве }

Этот же алгоритм можно реализовать в виде функции:

function countlevel(p : ptr; level, current : integer) : integer;
var n;
begin
	if p=nil then countlevel := 0
	else 
	begin
	n := countlevel(p^.llink, level, current+1) 
		+ countlevel(p^.rlink, level, current+1);
	if current=level then n := n+1;
		countlevel := n;
	end
 end;

Использование функции подсчета:

{ root указывает на корень дерева, level равно заданному уровню }
k := countlevel(root, level, 0);
{ k равно числу узлов в дереве }

Печать бинарного дерева на экране

Задача: распечатать бинарное дерево на экране так, чтобы узлы, составляющие левое (правое) поддерево для данного узла, были распечатаны на экране ниже и левее (правее) данного узла.

Алгоритм основан на b-обходе (ЛКП). При попадании в узел сначала рекурсивно печатаем его левое поддерево, затем сам узел, затем его правое поддерево. Положение узла по вертикали (которое зависит от его уровня) передается в качестве параметра процедуры и увеличивается при переходе к более глубокому уровню. (Для работы процедуры необходимо подключить модуль crt, из которого используется процедура gotoxy для помещения курсора в заданную позицию на экране и функция wherex для получения текущей позиции курсора по горизонтали).

procedure printtree(p : ptr; h : integer);
{ h - строка, на которой печатается узел }
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;

Например, для распечатки дерева, на корень которого указывает root, начиная со строки 10, нужно вызвать процедуру:

printtree(root, 10);

Удаление бинарного дерева

Задача: удалить все узлы бинарного дерева.

Алгоритм основан на g-обходе (ЛПК). При попадании в узел сначала рекурсивно удаляем его левое поддерево, затем правое поддерево, и только затем удаляем сам узел. (Для сравнения рядом с процедурой удаления приведена процедура g-обхода):

удаление дерева

procedure deltree(var p : ptr);
begin 
	if p<>nil then 
	begin 
		deltree(p^.llink);	
		deltree(p^.rlink); 
		dispose(p); 
		p := nil; 
	end;
end;

g-обход

procedure lpk(p : ptr);
begin 
	if p <> nil then 
	begin 
		lpk(p^.llink);	
		lpk(p^.rlink); 
		write(p^.info);
	end;
end;

(параметр процедуры удаления передается по ссылке для того, чтобы после удаления дерева фактический параметр - указатель на корень дерева - получил значение nil)

Использование процедуры удаления:

{ root указывает на корень дерева }
deltree(root);
{ root равен nil }

Зеркальное отражение дерева

Задача: превратить бинарное дерево в его зеркальное отражение, не создавая и не удаляя узлов, а только изменяя связи между ними. То есть, например, превратить дерево:

в дерево

Алгоритм основан на a или g-обходе. В случае a-обхода при попадании в узел сначала меняем местами указатели на его левое и правое поддеревья, после чего обрабатываем поддеревья. В случае g-обхода при попадании в узел сначала обрабатываем его поддеревья, а затем меняем местами указатели на левое и правое поддеревья. (b-обход здесь не подходит, так как при его использовании будет обрабатываться для каждого узла только одно поддерево). Пример процедуры, зеркально отражающей дерево, основанной на a-обходe:

procedure mirror(p : ptr);
var q : ptr;
begin
	if p <> nil then
	begin
		q := p^.llink;
		p^.llink := p^.rlink;
		p^.rlink := q;
		mirror(p^.llink);
		mirror(p^.rlink);
	end;
end;

Обработка узлов в порядке a, b и g-обходов с помощью одной процедуры

Если все узлы некоторого дерева нужно обработать в порядке a, b и g-обходов, то в некоторых случаях для этого достаточно одной процедуры следующего вида:

procedure all(p : ptr);
begin
	if p <> nil then
	begin
		{ выполняем действия при первом попадании в узел }
		all(p^.llink);
		{ выполняем действия при втором попадании в узел }
		all(p^.rlink);
		{ выполняем действия при третьем попадании в узел }
	end;
end;
 

Ясно, что таким образом можно объединять только те обходы, у которых совпадает порядок обработки левого и правого поддерева. То есть, например, можно построить общую процедуру для КЛП и ЛКП обходов, но нельзя построить общую процедуру для КЛП и ПКЛ обходов.

В качестве примера объединенной процедуры приведем процедуру, которая для заданного дерева печатает на экране в строке 1 его КЛП-обход, в строке 2 - ЛКП-обход, в строке 3 - ЛПК-обход и удаляет дерево:

procedure AllObhod(p : ptr);
begin
	if p <> nil then
	begin
		gotoxy(wherex, 1);
		write(p^.info);
		AllObhod(p^.llink);
		gotoxy(wherex, 2);
		write(p^.info);
		AllObhod(p^.rlink);
		gotoxy(wherex, 3);
		write(p^.info);
		dispose(p);
	end;
end;

Сравнение бинарных деревьев

Задача: даны два бинарных дерева. Написать функцию, возвращающую true, если они равны (то есть имеют одинаковую структуру и значения информационных полей узлов), и FALSE, если не равны.

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

function equal(p1, p2 : ptr) : boolean;
begin
	if (p1=nil) and (p2=nil) then equal := true
	else if (p1<>nil) and (p2<>nil) 
		then equal := (p1^.info= p2^.info) and equal(p1^.llink, p2^.llink) 
					  and equal(p1^.rlink, p2^.rlink)
	else equal := false
end;

Копирование бинарного дерева

Задача: по существующему дереву построить дерево-копию.

Пусть root1 - указатель на корень существующего дерева; root2 до выполнения алго-ритма равен nil, после выполнения указывает корень дерева-копии. Алгоритм копирования основан на a-обходе (КЛП). При попадании в каждый из узлов при обходе исходного де-рева создается очередной узел дерева-копии. (Для сравнения рядом с процедурой копиро-вания приведена процедура a-обхода):

копирование дерева

procedure copy(p1:ptr; var p2:ptr);
begin
	if  p1<>nil  then
	begin
		new(p2);
		p2^.info:= p1^.info;
		If  p1^.llink<>nil  then 
			copy(p1^.llink, p2^.llink)
		else 
			p2^.llink:=nil;
		If  p1^.rlink<>nil  then 
			copy(p1^.rlink, p2^.rlink)
		else 
			p2^.rlink:=nil;
	end;
end;

a-обход

procedure klp(p : ptr);
begin	
	if p <> nil then	
	begin	
		write(p^.info);	
		klp(p^.llink);	
		klp(p^.rlink);
	end;
end;

Использование процедуры копирования:

{ root1 указывает на корень исходного дерева }
root2 := nil;
copy(root1, root2);
{ root2 указывает на корень дерева копии }

(Пройти алгоритм по шагам на примере дерева:

)

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

function copy(p:ptr) : ptr;
var temp : ptr;
begin
	if p<>nil then
	begin
		new(temp);
		temp^.info := p^.info;
		temp^.llink := copy(p^.llink);
		temp^.rlink := copy(p^.rlink);
		copy := temp;
	end;
	else copy := nil;
end;

Использование функции копирования:

{ root1 указывает на корень исходного дерева }
root2 := copy(root1);
{ root2 указывает на корень дерева копии }

Поиск предшественника/преемника заданного узла при заданном обходе

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

Алгоритм поиска следующий. Вводится дополнительный указатель pold (указатель на предшествующий текущему узел) с начальным значением nil. Выполняется заданный обход. При попадании в каждый узел p проверяем, не совпадает ли его информационное поле с заданным значением (пусть это значение хранится в переменной sym). Если p^.info = sym, то pold указывает на предшественника, а следующий после p узел в обходе - преемник. В любом случае выполняем pold := p и продолжаем обход. Например, для поиска предшественника/преемника при b-обходе может быть использована следующая процедура:

procedure PrevNext_lkp(p : ptr; sym : char; var pold, prev, next : ptr);
{ p - указатель на узел дерева; sym - заданное значение в информационном поле;
pold - вспомогательный указатель;
prev - после выполнения указывает на предшественника; next - на преемника; }
begin
	if p<>nil then
	begin
		PrevNext_lkp(p^.llink, sym, pold, prev, next);
		if p^.info=sym then prev := pold;
		if (pold<>nil) and (pold^.info=sym) then next := p;
		pold := p;
		PrevNext_lkp(p^.rlink, sym, pold, prev, next);
	end;
end;

Пример поиска предшественника и преемника узла, содержащего в информационном поле символ 'F':

{ var root, ppold, pprev, pnex : ptr;
root указывает на корень дерева }
pold := nil; prev := nil; next := nil;
PrevNext_lkp(root, 'F', ppold, pprev, pnext);
{ После выполнения pprev указывает на предшественника, pnext на преемника. Если 
узла, со-держащего 'F' нет, то pprev=nil, pnext=nil. Если узел, содержащий 'F',   
самый первый в обходе, то pprev=nil, pnext<>nil; если самый последний  
в обходе, то pprev<>nil, pnext=nil }

Литература

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

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