Форум программистов, компьютерный форум CyberForum.ru

Обход дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 5.00
thick_int
Заблокирован
03.05.2012, 18:15     Обход дерева #1
Вот начал читать про деревья и способы их обхода (PreOrder, InOrder и PostOrder).
С алгоритмами проблем нет, но видно, как бы это сказать поточнее, не хватает что ли пространственного воображения, чтобы представить в чем суть каждого способа обхода.

Хотелось бы получить яркий пример, не обязательно, связанный с программированием, который демонстрирует разницу в методах обхода.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2012, 18:15     Обход дерева
Посмотрите здесь:

C++ обход дерева
Обход дерева C++
C++ обход дерева
Обход дерева) C++
обход дерева C++
C++ Обход дерева Хаффмана
обход дерева C++
C++ обход дерева

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
softonet
 Аватар для softonet
32 / 32 / 2
Регистрация: 17.04.2011
Сообщений: 201
03.05.2012, 18:21     Обход дерева #2
Существует 3 вида обхода дерева: прямой, обратный и концевой.

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

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

3) Концевой обход дерева
- пройти левое поддерево
- пройти правое поддерево
- попасть в корень
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
В силу рекурсивности струтктуры двоичного дерева, реализация алгоритма обхода очень проста.
 
Прямой
 
 
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);
}
thick_int
Заблокирован
03.05.2012, 18:24  [ТС]     Обход дерева #3
Ну это понятно то. Хотелось бы, так сказать, увидеть "физический смысл" каждого типа обхода, чтобы понять, когда и зачем какой из них применять.
Yandex
Объявления
03.05.2012, 18:24     Обход дерева
Ответ Создать тему
Опции темы

Текущее время: 09:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru