Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
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); | ||
} | |||||
} |
Дата публикования: 2014-11-04; Прочитано: 369 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!