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

Поперечное прохождение бинарного дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
31.07.2013, 08:40     Поперечное прохождение бинарного дерева #1
Собственно вопрос такой. В каком порядке при этом происходит обход бинарного дерева и как это может быть реализовано. Про обратный, симметричный и прямой обход поисковик выдал много материалов, про этот вид обходи статей не нашел
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.07.2013, 08:40     Поперечное прохождение бинарного дерева
Посмотрите здесь:

Построение бинарного дерева C++
C++ Построение бинарного дерева на основе не бинарного
C++ Вывод бинарного дерева
Построение бинарного дерева C++
C++ Вывод бинарного дерева на экран в виде "дерева"
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
maks_b
4 / 4 / 0
Регистрация: 11.10.2011
Сообщений: 15
31.07.2013, 20:09     Поперечное прохождение бинарного дерева #2
Прямой порядок:
1. Обращение к узлу.
2. Рекурсивный прямой обход левого поддерева.
3. Рекурсивный прямой обход правого поддерева.
Симметричный порядок:
1. Рекурсивный симметричный обход левого поддерева.
2. Обращение к узлу.
3. Рекурсивный симметричный обход правого поддерева.
Обратный порядок:
1. Рекурсивный обратный обход левого поддерева.
2. Рекурсивный обратный обход правого поддерева.
3. Обращение к узлу.

Добавлено через 9 минут
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
75
76
77
78
#include <iostream>
using namespace std;
 
struct TreeNode{
    int key;
    TreeNode *Left,*Right,*Parent;
};
void show(TreeNode *tmp)//Прямой порядок
{
    if(!tmp)return;
        cout<<tmp->key<<endl; 
    if(tmp->Left)
        show(tmp->Left);
    
    if(tmp->Right)
    show(tmp->Right);
    
}
void show2(TreeNode *tmp)//Симметричный
{
    if(!tmp)return;
    if(tmp->Left)
    show2(tmp->Left);
    cout<<tmp->key<<endl;
    if(tmp->Right)
    show2(tmp->Right);
    
}
void show3(TreeNode *tmp)//Обратный порядок
{
    if(!tmp)return;
    if(tmp->Left)
    show3(tmp->Left);
        if(tmp->Right)
    show3(tmp->Right);
    cout<<tmp->key<<endl;
    
    
}
void AddNode(TreeNode *&pTree, int Key,TreeNode *Parent)
{
    if (pTree)
    {
        if (Key < pTree->key){
        AddNode(pTree->Left, Key,pTree);}
        else if (Key > pTree->key){
        AddNode(pTree->Right, Key,pTree);}
        
    }
    else{
        pTree = new TreeNode();
        pTree->key = Key;
        pTree->Parent=Parent;
                pTree->Left=NULL;
                pTree->Right=NULL;
    }
}
 
int main(){
    int key=1, kolichesto,i=0;
    cin>>kolichesto;// вводится количество элементов в дереве
    TreeNode *tree = NULL; 
    
    while(i<kolichesto){
        cin>>key;
        AddNode(tree, key, NULL);
        i++;
    }
    if(tree!=NULL){
        show(tree);
                cout<<endl;
                show2(tree);
                cout<<endl;
                show3(tree);
    }
    cin>>key;
    return 0;
}
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
31.07.2013, 20:13     Поперечное прохождение бинарного дерева #3
_Колючий_, если имеется в виду обход в ширину (последовательно по уровням), то: создаём очередь, добавляем туда корень дерева; пока очередь не пуста, достаем узел из очереди, добавляем в очередь детей узла.
maks_b
4 / 4 / 0
Регистрация: 11.10.2011
Сообщений: 15
31.07.2013, 20:14     Поперечное прохождение бинарного дерева #4
я не дочитал вопрос)
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
31.07.2013, 20:18     Поперечное прохождение бинарного дерева #5
Примерно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if (root) {
   std::queue<tree_node *> queue;
   queue.push(root);
 
   while (!queue.empty()) {
      tree_node * current = queue.top();
      queue.pop();
 
      if (current->left) {
         queue.push(current->left);
      }
      if (current->right) {
         queue.push(current->right);
      }
 
      do_stuff(current);
   }
}
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
01.08.2013, 15:18  [ТС]     Поперечное прохождение бинарного дерева #6
Цитата Сообщение от gray_fox Посмотреть сообщение
_Колючий_, если имеется в виду обход в ширину (последовательно по уровням), то: создаём очередь, добавляем туда корень дерева; пока очередь не пуста, достаем узел из очереди, добавляем в очередь детей узла.
Спасибо. Честно говоря не в курсе, что имеется в виду, поэтому и спрашиваю

Но так-то логично, что поперечный обход - это обход по "строкам" дерева.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.08.2013, 15:40     Поперечное прохождение бинарного дерева #7
дерево растет сверху вниз.
- прямой обход: обход дерева сверху вниз (сначала узел, а потом его потомки)
- обратный обход: обход дерева снизу вверх (сначала потомки узла, а потом сам узел)
- поперечный обход: обход дерева слева направо (сначала посещаем левого потомка, потом текущий узел, а потом правого потомка). можно обходить и справа налево. он еще называется симметричным обходом
- обход по уровням: обход дерева построчно (сначала корень дерева, потом все его дети, потом все его внуки, потом все его правнуки и т.д.)
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
01.08.2013, 20:22  [ТС]     Поперечное прохождение бинарного дерева #8
Цитата Сообщение от ya_noob Посмотреть сообщение
дерево растет сверху вниз.
- прямой обход: обход дерева сверху вниз (сначала узел, а потом его потомки)
- обратный обход: обход дерева снизу вверх (сначала потомки узла, а потом сам узел)
- поперечный обход: обход дерева слева направо (сначала посещаем левого потомка, потом текущий узел, а потом правого потомка). можно обходить и справа налево. он еще называется симметричным обходом
- обход по уровням: обход дерева построчно (сначала корень дерева, потом все его дети, потом все его внуки, потом все его правнуки и т.д.)
Ну не знаю. У меня в билете прямо написано:

Прямое, обратное, симметричное и поперечное прохождение бинарного дерева.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.08.2013, 21:04     Поперечное прохождение бинарного дерева #9
я указал все возможные стратегии обхода. википедия со мной согласна: http://ru.wikipedia.org/wiki/Дерево_...BE.D0.B4.D0.B0
Цитата Сообщение от _Колючий_ Посмотреть сообщение
симметричное и поперечное прохождение бинарного дерева.
это одно и то же.
вот еще вам ссылка: http://www.rsdn.ru/article/alg/binstree.xml#ESC
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.08.2013, 15:22     Поперечное прохождение бинарного дерева
Еще ссылки по теме:

Написать шаблон бинарного дерева с функцией распечатки дерева C++
C++ Высота бинарного дерева
C++ Запись бинарного дерева

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

Или воспользуйтесь поиском по форуму:
_Колючий_
3 / 3 / 2
Регистрация: 05.08.2012
Сообщений: 88
02.08.2013, 15:22  [ТС]     Поперечное прохождение бинарного дерева #10
Цитата Сообщение от ya_noob Посмотреть сообщение
я указал все возможные стратегии обхода. википедия со мной согласна: http://ru.wikipedia.org/wiki/Дерево_...BE.D0.B4.D0.B0

это одно и то же.
вот еще вам ссылка: http://www.rsdn.ru/article/alg/binstree.xml#ESC
Учту

Все-таки поинтересуюсь у преподавателей, что им нужно. Не исключено, что описались.
Yandex
Объявления
02.08.2013, 15:22     Поперечное прохождение бинарного дерева
Ответ Создать тему
Опции темы

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