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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
_Колючий_
4 / 4 / 2
Регистрация: 05.08.2012
Сообщений: 105
#1

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

31.07.2013, 08:40. Просмотров 1760. Ответов 9
Метки нет (Все метки)

Собственно вопрос такой. В каком порядке при этом происходит обход бинарного дерева и как это может быть реализовано. Про обратный, симметричный и прямой обход поисковик выдал много материалов, про этот вид обходи статей не нашел
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.07.2013, 08:40     Поперечное прохождение бинарного дерева
Посмотрите здесь:

Построение бинарного дерева из строки - C++
Доброго времени суток, уважаемые. Хотел бы спросить у вас спросить совета относительно реализации следующей проблемы: Задано...

Обходы бинарного дерева, рекурсивные и не. - C++
#include <stdlib.h> #include <stdio.h> #include <iostream> #include <string.h> using namespace std;

Удаление вершины бинарного дерева - C++
Как удалять вершины бинарного дерева вместе с потомками?

Класс для бинарного дерева - C++
Здравствуйте! Помогите, пожалуйста, я не вижу ошибок и не понимаю, почему программа не видит меню, не работает так, как нужно( Общее...

Удаление узла бинарного дерева - C++
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени помогите плиз. .cpp #include <iostream>...

Проблемы с выводом бинарного дерева - C++
Вот, пытался сделать лабу. Проблема с выводом. Извините за код, знаю что он кривой, сделайте замечания!!! /* Два бинарных дерева...

Печать листьев бинарного дерева - C++
Всем привет! Решаю такую задачу: На входе - последовательность целых чисел, оканчивающаяся 0, который является символом завершения...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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!
1411 / 1140 / 55
Регистрация: 21.04.2012
Сообщений: 2,362
Завершенные тесты: 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!
1411 / 1140 / 55
Регистрация: 21.04.2012
Сообщений: 2,362
Завершенные тесты: 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);
   }
}
_Колючий_
4 / 4 / 2
Регистрация: 05.08.2012
Сообщений: 105
01.08.2013, 15:18  [ТС]     Поперечное прохождение бинарного дерева #6
Цитата Сообщение от gray_fox Посмотреть сообщение
_Колючий_, если имеется в виду обход в ширину (последовательно по уровням), то: создаём очередь, добавляем туда корень дерева; пока очередь не пуста, достаем узел из очереди, добавляем в очередь детей узла.
Спасибо. Честно говоря не в курсе, что имеется в виду, поэтому и спрашиваю

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

Прямое, обратное, симметричное и поперечное прохождение бинарного дерева.
ya_noob
_
201 / 145 / 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++
#include &lt;stdlib.h&gt; #include &lt;iostream&gt; struct uzel { int key;//хранится в вершине ключ-значение struct uzel...

Использование целочисленного бинарного дерева - C++
Всем привет. Снова проблема с задачей, помогите пожалуйста. Дано целочисленное бинарное дерево. Найти: а) глубину дерева - ...

Реализация бинарного дерева классом - C++
Добрый вечер. Написал класс class TreeClass { int number; TreeClass *left, *right; public: void AddNode(int, TreeClass); ...

Написать сортировку бинарного дерева - C++
Как записать функцию, которая сортирует элементы бинарного дерева по возрастанию?Подскажите пожалуйста


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

Или воспользуйтесь поиском по форуму:
_Колючий_
4 / 4 / 2
Регистрация: 05.08.2012
Сообщений: 105
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     Поперечное прохождение бинарного дерева
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru