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

Бинарные деревья и стек отл. заданий - C++

Восстановить пароль Регистрация
 
Frukt521
0 / 0 / 0
Регистрация: 02.07.2012
Сообщений: 5
02.07.2012, 22:37     Бинарные деревья и стек отл. заданий #1
Доброго времени суток. Ребят, я не спец, требуется решить такую задачу:

Написать нерекурсивную программу, печатающую все вершины двоичного дерева. При реализации использовать стек отложенных заданий.Узлы дерева – символы латинского алфавита.
Дерево задается в файле в формате:
m [e [c [a], g [k] ], s [p [o,s], y ] ]
Рисунок, поясниющий пример:
Бинарные деревья и стек отл. заданий

Прошу помочь
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.07.2012, 22:37     Бинарные деревья и стек отл. заданий
Посмотрите здесь:

Бинарные деревья C++
Бинарные деревья C++
Бинарные деревья C++
бинарные деревья C++
Бинарные деревья C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
02.07.2012, 22:57     Бинарные деревья и стек отл. заданий #2
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
struct node {
    char data;
    node *left, *right;
    int visited;
    node() : visited(0) {}
};
 
void print(node *root) {
    if (!root) {
        std::cout << "Tree is empty.";
        return;
    }
    std::stack <node *> stack;
    stack.push(root);
    root->visited = 1;
    node *cur;
    while (!stack.empty()) {
        cur = stack.top();
        if (cur->left && !cur->left->visited) {
            stack.push(cur->left);
            cur->left->visited = 1;
        } else if (cur->right && !cur->right->visited) {
            stack.push(cur->right);
            cur->right->visited = 1;
        } else {
            std::cout << cur->data << " ";
            stack.pop();
        }
    }
}
что-то не сообразить мне сразу как без дополнительного поля обойтись)
Frukt521
0 / 0 / 0
Регистрация: 02.07.2012
Сообщений: 5
02.07.2012, 23:16  [ТС]     Бинарные деревья и стек отл. заданий #3
neske, спасибо, будем пробовать, еще бы знать как забить данные, каким образом организовать цикл?
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
02.07.2012, 23:22     Бинарные деревья и стек отл. заданий #4
данные рекурсивно забить можно, к примеру дано - m [e [c [a], g [k] ], s [p [o,s], y ] ]
m - корень
e [c [a], g [k] ] - левое поддерево
s [p [o,s], y ] - правое поддерево
и так спускайтесь, пока не дойдете до внешних узлов
Frukt521
0 / 0 / 0
Регистрация: 02.07.2012
Сообщений: 5
02.07.2012, 23:27  [ТС]     Бинарные деревья и стек отл. заданий #5
устройство то понятно, а вот как функцию организовать без рекурсии - нет(
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
02.07.2012, 23:31     Бинарные деревья и стек отл. заданий #6
почему без рекурсии? в задании же сказано только про итерационный вывод дерева
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.07.2012, 23:36     Бинарные деревья и стек отл. заданий
Еще ссылки по теме:

C++ Бинарные деревья
C++ Бинарные деревья
бинарные деревья С++ C++

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

Или воспользуйтесь поиском по форуму:
Frukt521
0 / 0 / 0
Регистрация: 02.07.2012
Сообщений: 5
02.07.2012, 23:36  [ТС]     Бинарные деревья и стек отл. заданий #7
"Написать нерекурсивную программу" , или я чего-то непонимаю
Yandex
Объявления
02.07.2012, 23:36     Бинарные деревья и стек отл. заданий
Ответ Создать тему
Опции темы

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