Дерево выражения и способы его обхода

Три способа обхода бинарного дерева

Прототипы функций

Программа

#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. Корень