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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 134, средняя оценка - 4.85
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
#1

НЕрекурсивный обход бинарного дерева - C++

24.09.2009, 12:35. Просмотров 17544. Ответов 15

уважаемые программисты!

нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с помощью стека.
Проверить на дереве int, но в самом коде испльзовать указатели на функцию - типа что дерево состоит из чего угодно...

Кто знает КАК ЭТО ДЕЛАТЬ НА СИ???
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2009, 12:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос НЕрекурсивный обход бинарного дерева (C++):

Нерекурсивный обход дерева - C++
я не могу понять как сделать не рекурсивный обход дерева. понятно что надо добавлять элементы куда-то.в стек например. но я не знаю как...

Обход Бинарного дерева - C++
Задача: написать функцию, помощью которой можно получить n-тый элемент бинарного дерева по возрастанию. в узлах хранятся целые числа. ...

Обход бинарного дерева С++ - C++
Нужна помощь! Просмотрел много источников, но так и не нашёл своего ответа...Суть задачи состоит в том что, мне нужно при обходе...

Обход бинарного дерева - C++
может есть у кого такой пример или похожий??или часть какая нибудь?

Обход бинарного дерева - C++
Прошу Вас, помогите школьнику, незнающему деревья, завтра срочно надо сдать работу, я никак не могу реализовать... 1. В заданном...

Обход бинарного дерева без рекурсии - C++
нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с помощью стека. Проверить на дереве int, но в самом коде...

15
Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
24.09.2009, 15:30 #2
Используйте шаблон и описывайте его как одноноправленный список.
хочешь примеров поисчи в гугл
0
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
24.09.2009, 15:41  [ТС] #3
как именно сформулировать чтобы искать?
0
R0mm
Псевдо программист
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
24.09.2009, 15:44 #4
поищите тут...
http://www.google.com/search?client=opera&rls=ru&q=%D0%B1%D0%B8%D0%BD%D0%B0%D1%80%D0%BD%D0%BE%D0%B5+%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE+%D0%B E%D0%B1%D1%85%D0%BE%D0%B4+%D1%81%D1%82%D0%B5%D0%BA&sourceid=opera&ie=utf-8&oe=utf-8
0
odip
Эксперт С++
7157 / 3219 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
24.09.2009, 20:16 #5
А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Если плохой, то не хочется расписывать

Если хороший, то алгоритм прост:
Берется рекурсивный алгоритм обхода дерева.
Как известно любое рекурсивное решение заменяется на такое же, но без рекурсии, но с использованием стека или очереди.
Поэтому там где в рекурсивном алгоритме идет вызов функции из самой себя нужно просто записать параметры вызова в стек и перейти на начало функции.
Если стек стал пуст - значит все закончено.
В самом начале нужно положить в стек узел - начало дерева.
0
Evg
Эксперт CАвтор FAQ
17934 / 6162 / 409
Регистрация: 30.03.2009
Сообщений: 16,918
Записей в блоге: 27
24.09.2009, 20:20 #6
Цитата Сообщение от odip Посмотреть сообщение
А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Обход бинарного дерева без рекурсии
0
Ёрик
46 / 46 / 2
Регистрация: 07.01.2009
Сообщений: 298
24.09.2009, 21:55 #7
Вообще дерево - это связный граф.Если реализовать обход дерева с помощью поиска в ширину(там нужна очередь),то получится без рекурсии
0
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
24.09.2009, 22:05  [ТС] #8
Это вы все правильно говорите, но мне бы код воочию увидеть, плизЗЗЗ!
0
SerЁga
32 / 32 / 4
Регистрация: 18.08.2009
Сообщений: 93
24.09.2009, 22:35 #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
#define N 80
 
struct der
{
    char inf[N];
    int n;
    der *l,*r;
};
 
void see_2(der *dr)
{
    struct stek
    {
        der *d;
        stek *s;
    } *st,*st1=NULL;
    der *dr1;
    dr1=dr;
    int pr=1,i=0;
    for(i=0;i<2;i++)
    {
        st=(stek*)calloc(1,sizeof(stek));
        st->d=dr1;
        st->s=st1;
        st1=st;
    }
    printf("uzel soderzhit %s %d vstrech\n",dr1->inf,dr1->n);
    while(st)
    {
        do
        {
            if(pr && dr1->l) dr1=dr1->l;
            else if(dr1->r) dr1=dr1->r;
            pr=1;
            if(dr1->l && dr1->r)
            {
                st=(stek*)malloc(sizeof(stek));
                st->d=dr1;
                st->s=st1;
                st1=st;
            }
            printf("uzel soderzhit %s %d vstrech\n",dr1->inf,dr1->n);
        } while(dr1->l || dr1->r);
        dr1=st->d;
        st1=st->s;
        free(st);
        st=st1;
        if(dr1->r) pr=0;
    }
}
0
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
25.09.2009, 05:24 #10
будем считать что я опаздал
0
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
25.09.2009, 08:12 #11
кстати, встретил идею записывать дерево как массив. тогда обход дерева становиться тревиальной задачей. вот отсюда почерпнул
0
Вложения
Тип файла: rar c-tricks-A.rar (7.8 Кб, 215 просмотров)
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
25.09.2009, 11:28  [ТС] #12
О! Спасибо!!!!
Мне правда задавали чтобы были фунции push и pop для помещения/удаления в стек....
0
Галла
15 / 15 / 0
Регистрация: 22.09.2009
Сообщений: 148
25.09.2009, 11:35 #13
natalia-82, http://window.edu.ru/window_catalog/...33770&p_page=5
0
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
25.09.2009, 11:37  [ТС] #14
и еще сказали, чтобы дерево содержало не строки, а что угодно, т.е. туда надо ввернуть указетель на функцию с void*
0
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
07.10.2009, 16:54  [ТС] #15
А как мне написать, чтобы было тоже самое, но с функциями push() и pop()? Они у меня уже есть написанные эти пуш и поп и стек я сделала в виде связ. списка. Вроде все понятно в теории, но опыта в программировании совсем нету
И мне надо вообще-то написать 3 обхода left-root-right, right-root-left, left-right-root.

Не судите строго - я новичок!
Всем заранее спасибо за помощь!!!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2009, 16:54
Привет! Вот еще темы с ответами:

Как осуществлять обход бинарного дерева? - C++
Хочу создать клас бинарное дерево, но не знаю чем это дерево я буду проходить, как двигатса от одного узла к дргому.(без создания...

Бинарное дерево. Обход бинарного дерева (симметрический, прямой и обратный) - C++
Привет всем! Мне надо в курсовой работе написать программу, которая строит бинарное дерево (по вводимым значениям) и потом обходит это...

"Рекурсивная функция" (Обход бинарного дерева) - C++
Привет всем, встретился с такой рекурсивной ф-ей, которая обходит бинарное дерево и выводит его на экран. Не могу понять как она работает ...

Запись бинарного дерева в файл и восстановление из него этого дерева - C++
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на структуру с данными, 2 и 3й указатель на...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
07.10.2009, 16:54
Ответ Создать тему
Опции темы

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