Дерево выражения и способы его обхода
Три способа обхода бинарного дерева
Прототипы функций
Программа
#include <stdio.h>
#include <stdlib.h>
/* Описание бинарного дерева в виде регулярной сети */
// Тип вершины дерева (элемента сети)
struct TREE
{ float number; // число
struct TREE *left, *right; /* указатели на левое и правое поддеревья*/
};
void insert (struct TREE *pt, float x);
void print_tree (struct TREE *pt);
void delete_tree (struct TREE *pt);
/*--------------------------------------*/
/* Главная функция */
/*--------------------------------------*/
void main()
{ struct TREE *pt; // указатель на корень дерева
float x; // очередное число
puts ("\nВведите числовую последовательность");
scanf("%f", &x);
// создание корня дерева
pt = (struct TREE *) malloc (sizeof(struct TREE));
pt->number=x;
pt->left=pt->right=NULL;
// ввод чисел и формирование дерева while (scanf("%f", &x) != EOF)
insert (pt,x);
// обход дерева и печать результата
puts ("Результат:");
print_tree (pt);
// удаление дерева
delete_tree (pt);
}
/*---------------------------------------------------------------------*/
/* Функция включения новой вершины в дерево */
/*---------------------------------------------------------------------*/
void insert (struct TREE *pt, float x)
// pt - указатель на корень дерева
// x – число - метка новой вершины
{ struct TREE *i, /* указатель на текущую вершину дерева */
*parent; /* указатель на вершину- родителя для новой вершины */
int dir; /* признак включения новой вершины
в левую или правую ветвь */
/* спуск по дереву и поиск вершины- родителя для новой вершины*/
i = pt;
while (i != NULL)
{ parent = i;
if (x < i->number) { // спуск влево
i = i->left; dir = 0; }
else { // спуск вправо
i = i->right; dir = 1; } }
/* создание новой вершины */
i = (struct TREE *) malloc (sizeof (struct TREE));
i->number = x;
i->left = i->right = NULL;
/* включение новой вершины в левую или правую ветвь родителя*/
if (dir == 0) parent->left = i;
else parent->right = i; }
/*---------------------------------------------------------------------*/
/* Рекурсивная функция обхода дерева слева */
/* направо и печати его вершин */
/*---------------------------------------------------------------------*/
void print_tree (struct TREE *pt)
/* pt - указатель на корень дерева (поддерева) */
{ if (pt)
{ print_tree (pt->left);
printf ("%f ", pt->number);
print_tree (pt->right);
}
}
/*-----------------------------------------------------------------*/
/* Рекурсивная функция обхода дерева снизу */
/* вверх и удаления его вершин */
/*-----------------------------------------------------------------*/
void delete_tree (struct TREE *pt)
// pt - указатель на корень дерева (поддерева)
{ if (pt)
{ delete_tree (pt->left);
delete_tree (pt->right);
free (pt);
}
}
Прямой обход (обход сверху вниз):
1. Корень
2. Левое поддерево
3. Правое поддерево
Внутренний обход (обход слева направо):
1. Левое поддерево
2. Корень
3. Правое поддерево
Обратный обход (обход снизу вверх):
1. Левое поддерево
2. Правое поддерево
3. Корень
