Узел дерева
struct tnode
{
char *word; /^указатель на поле info*/
struct tnode *left; /*левый потомок*/ struct tnode *right; /*правый потомок*/
Instruct 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) ; | ||
} | |||||
} |