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

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

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

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

Кто знает КАК ЭТО ДЕЛАТЬ НА СИ???
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sekt
 Аватар для Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
24.09.2009, 15:30     НЕрекурсивный обход бинарного дерева #2
Используйте шаблон и описывайте его как одноноправленный список.
хочешь примеров поисчи в гугл
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
24.09.2009, 15:41  [ТС]     НЕрекурсивный обход бинарного дерева #3
как именно сформулировать чтобы искать?
R0mm
Псевдо программист
 Аватар для 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%BE%D0%B1%D1%85%D0%BE%D0%B4+%D1%81%D1%82%D0%B5%D0%BA&sourceid=opera&ie=utf-8&oe=utf-8
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
24.09.2009, 20:16     НЕрекурсивный обход бинарного дерева #5
А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Если плохой, то не хочется расписывать

Если хороший, то алгоритм прост:
Берется рекурсивный алгоритм обхода дерева.
Как известно любое рекурсивное решение заменяется на такое же, но без рекурсии, но с использованием стека или очереди.
Поэтому там где в рекурсивном алгоритме идет вызов функции из самой себя нужно просто записать параметры вызова в стек и перейти на начало функции.
Если стек стал пуст - значит все закончено.
В самом начале нужно положить в стек узел - начало дерева.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
24.09.2009, 20:20     НЕрекурсивный обход бинарного дерева #6
Цитата Сообщение от odip Посмотреть сообщение
А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Обход бинарного дерева без рекурсии
Ёрик
45 / 45 / 2
Регистрация: 07.01.2009
Сообщений: 298
24.09.2009, 21:55     НЕрекурсивный обход бинарного дерева #7
Вообще дерево - это связный граф.Если реализовать обход дерева с помощью поиска в ширину(там нужна очередь),то получится без рекурсии
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
24.09.2009, 22:05  [ТС]     НЕрекурсивный обход бинарного дерева #8
Это вы все правильно говорите, но мне бы код воочию увидеть, плизЗЗЗ!
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;
    }
}
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
25.09.2009, 05:24     НЕрекурсивный обход бинарного дерева #10
будем считать что я опаздал
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
25.09.2009, 08:12     НЕрекурсивный обход бинарного дерева #11
кстати, встретил идею записывать дерево как массив. тогда обход дерева становиться тревиальной задачей. вот отсюда почерпнул
Вложения
Тип файла: rar c-tricks-A.rar (7.8 Кб, 202 просмотров)
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
25.09.2009, 11:28  [ТС]     НЕрекурсивный обход бинарного дерева #12
О! Спасибо!!!!
Мне правда задавали чтобы были фунции push и pop для помещения/удаления в стек....
Галла
 Аватар для Галла
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
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
25.09.2009, 11:37  [ТС]     НЕрекурсивный обход бинарного дерева #14
и еще сказали, чтобы дерево содержало не строки, а что угодно, т.е. туда надо ввернуть указетель на функцию с void*
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.

Не судите строго - я новичок!
Всем заранее спасибо за помощь!!!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.12.2011, 03:01     НЕрекурсивный обход бинарного дерева
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Goldcoding
3 / 3 / 0
Регистрация: 04.01.2010
Сообщений: 46
01.12.2011, 03:01     НЕрекурсивный обход бинарного дерева #16
Вот, как пример есть программа строящая бинарное дерево и выполняющая его обход в ширину. (без рекурсии)
Yandex
Объявления
01.12.2011, 03:01     НЕрекурсивный обход бинарного дерева
Ответ Создать тему

Метки
деревья, структуры данных
Опции темы

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