Обход дерева

Существует 3 вида обхода дерева: прямой, обратный и концевой.

1) Прямой обход дерева
- попасть в корень
- пройти левое поддерево
- пройти правое поддерево

2) Обратный обход дерева
- пройти левое поддерево
- попасть в корень
- пройти правое поддерево

3) Концевой обход дерева
- пройти левое поддерево
- пройти правое поддерево
- попасть в корень

В силу рекурсивности струтктуры двоичного дерева, реализация алгоритма обхода очень проста.

Прямой

struct Node{
char *info; // информация, располагаемая в узле дерева
Node *left; // указатель на левое поддерево
Node *right; // указатель на правое поддерево
};
int cnt; // порядковый номер узла дерева в процессе обхода

void straight(Node *root)
{
if(!root)
return;
/* здесь выполняется необходимая обработка корня – например, вывод информации в выходной поток */
printf("%d. \"%s\"\n", ++cnt, root->info);
/* обход левого поддерева */
straight(root->left);
/* обход правого поддерева */
straight(root->right);
}


Обратный

struct Node{
char *info; /* информация, располагаемая в узле дерева */
Node *left; /* указатель на левое поддерево */
Node *right; /* указатель на правое поддерево */
};
int cnt;

void reverse(Node *root)
{
/* если дерево пусто, не выполнять никаких действий – обход дерева завершается
*/
if(!root)
return;
/* обход левого поддерева */
reverse(root->left);
/* здесь выполняется необходимая обработка корня – например,
вывод информации в выходной поток */
printf("%d. \"%s\"\n", ++cnt, root->info);
/* обход правого поддерева */
reverse(root->right);
}


Концевой

struct Node{
char *info; /* информация, располагаемая в узле дерева */
Node *left; /* указатель на левое поддерево */
Node *right; /* указатель на правое поддерево */
};
int cnt;

void tail(Node *root)
{
/* если дерево пусто, не выполнять никаких действий – обход дерева завершается
*/
if(!root)
return;
/* обход левого поддерева */
tail(root->left);
/* обход правого поддерева */
tail(root->right);
/* здесь выполняется необходимая обработка корня – например,
вывод информации в выходной поток */
printf("%d. \"%s\"\n", ++cnt, root->info);
}