Обход дерева

В силу рекурсивности струтктуры двоичного дерева, реализация алгоритма обхода очень проста.
 
Прямой
 
 
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);
}