Узел дерева

struct tnode

{

char *word; /^указатель на поле info*/

struct tnode *left; /*левый потомок*/ struct tnode *right; /*правый потомок*/

In­struct tnode *root;

/^указатель на узел*/

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

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

Пусть имеем дерево, где R — корень, А и В — левое и правое поддеревья (рис. 2.16). Существует три способа обхода дерева:

1. Обход дерева сверху вниз (в прямом порядке): R, А, В.

2. В симметричном порядке (слева направо): A, R, В.

3. В обратном порядке (снизу вверх): А, В, R. Функции обхода дерева удобно выразить рекурсивно.

Рис. 2.16. Дерево

Пример. Пусть имеем дерево для арифметического следующего выражения (рис. 2.17):

(a + b/c)*(d-e*f).

Обходя дерево выписывая символы в узлах в том порядке, как они встречаются, получаем:

1. Сверху вниз: *+a/bc-d*ef — префиксная запись выражения.

2. Слева направо: a+b/c*d-e*f — инфиксная запись без скобок, которые
определяют порядок действий.

3. Снизу вверх: abc/+dej*-* — постфиксная запись.

Рис. 2.17. Дерево

Эти три способа обхода легко сформулировать в виде функций. Функция обхода дерева сверху вниз

voi	-d ]	oreorder
{
if	(t {	!=NULL) P(t);
		preorder	(t-	->le	ft);
		preorder	(t-	->ri	ght);
	}
}

Дата добавления: 2014-11-29