Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.70/104: Рейтинг темы: голосов - 104, средняя оценка - 4.70
natalia-82
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
1

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

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

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

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

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

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

Нерекурсивный прямой обход BST дерева
Дайте пожалуйста пример реализации НЕрекурсивного прямого обхода дерева

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

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

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

15
Sekt
157 / 156 / 47
Регистрация: 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 / 37
Регистрация: 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
Эксперт С++
7162 / 3221 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
24.09.2009, 20:16 5
А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Если плохой, то не хочется расписывать

Если хороший, то алгоритм прост:
Берется рекурсивный алгоритм обхода дерева.
Как известно любое рекурсивное решение заменяется на такое же, но без рекурсии, но с использованием стека или очереди.
Поэтому там где в рекурсивном алгоритме идет вызов функции из самой себя нужно просто записать параметры вызова в стек и перейти на начало функции.
Если стек стал пуст - значит все закончено.
В самом начале нужно положить в стек узел - начало дерева.
0
Evg
Эксперт CАвтор FAQ
19288 / 7147 / 528
Регистрация: 30.03.2009
Сообщений: 19,997
Записей в блоге: 30
24.09.2009, 20:20 6
Цитата Сообщение от odip Посмотреть сообщение
А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Обход бинарного дерева без рекурсии
0
Ёрик
46 / 46 / 3
Регистрация: 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 / 16
Регистрация: 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
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
25.09.2009, 05:24 10
будем считать что я опаздал
0
TanT
эволюционирую потихоньку
467 / 465 / 91
Регистрация: 30.06.2009
Сообщений: 1,399
25.09.2009, 08:12 11
кстати, встретил идею записывать дерево как массив. тогда обход дерева становиться тревиальной задачей. вот отсюда почерпнул
0
Вложения
Тип файла: rar c-tricks-A.rar (7.8 Кб, 221 просмотров)
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/pdf2txt?p_id=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
Goldcoding
3 / 3 / 0
Регистрация: 04.01.2010
Сообщений: 46
01.12.2011, 03:01 16
, как пример есть программа строящая бинарное дерево и выполняющая его обход в ширину. (без рекурсии)
0
01.12.2011, 03:01
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.12.2011, 03:01

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

Обход бинарного дерева без рекурсии
нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с...

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


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

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