Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.89/141: Рейтинг темы: голосов - 141, средняя оценка - 4.89
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
1

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

24.09.2009, 12:35. Показов 26230. Ответов 15

Author24 — интернет-сервис помощи студентам
уважаемые программисты!

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

Кто знает КАК ЭТО ДЕЛАТЬ НА СИ???
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.09.2009, 12:35
Ответы с готовыми решениями:

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

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

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

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

15
159 / 156 / 47
Регистрация: 29.04.2009
Сообщений: 636
24.09.2009, 15:30 2
Используйте шаблон и описывайте его как одноноправленный список.
хочешь примеров поисчи в гугл
0
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
24.09.2009, 15:41  [ТС] 3
как именно сформулировать чтобы искать?
0
Псевдо программист
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+%D 0%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%D 0%B5%D0%BA&sourceid=opera&ie=utf-8&oe=utf-8
0
Эксперт С++
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
24.09.2009, 20:16 5
А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Если плохой, то не хочется расписывать

Если хороший, то алгоритм прост:
Берется рекурсивный алгоритм обхода дерева.
Как известно любое рекурсивное решение заменяется на такое же, но без рекурсии, но с использованием стека или очереди.
Поэтому там где в рекурсивном алгоритме идет вызов функции из самой себя нужно просто записать параметры вызова в стек и перейти на начало функции.
Если стек стал пуст - значит все закончено.
В самом начале нужно положить в стек узел - начало дерева.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
24.09.2009, 20:20 6
Цитата Сообщение от odip Посмотреть сообщение
А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Обход бинарного дерева без рекурсии
0
47 / 47 / 3
Регистрация: 07.01.2009
Сообщений: 297
24.09.2009, 21:55 7
Вообще дерево - это связный граф.Если реализовать обход дерева с помощью поиска в ширину(там нужна очередь),то получится без рекурсии
0
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
24.09.2009, 22:05  [ТС] 8
Это вы все правильно говорите, но мне бы код воочию увидеть, плизЗЗЗ!
0
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
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
25.09.2009, 05:24 10
будем считать что я опаздал
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
25.09.2009, 08:12 11
кстати, встретил идею записывать дерево как массив. тогда обход дерева становиться тревиальной задачей. вот отсюда почерпнул
Вложения
Тип файла: rar c-tricks-A.rar (7.8 Кб, 243 просмотров)
1
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_ca... 0&p_page=5
0
0 / 0 / 0
Регистрация: 23.09.2009
Сообщений: 8
25.09.2009, 11:37  [ТС] 14
и еще сказали, чтобы дерево содержало не строки, а что угодно, т.е. туда надо ввернуть указетель на функцию с void*
0
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
3 / 3 / 0
Регистрация: 04.01.2010
Сообщений: 46
01.12.2011, 03:01 16
, как пример есть программа строящая бинарное дерево и выполняющая его обход в ширину. (без рекурсии)
0
01.12.2011, 03:01
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.12.2011, 03:01
Помогаю со студенческими работами здесь

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

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

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

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

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

Обход правой части бинарного дерева (корень - уникальный элемент)
Здравствуйте, уважаемые форумчане! Снова придумал несложную задачу на бинарные деревья. Надеюсь,...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru