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

@natalia-82 · Регистрация: 23.09.2009

Студворк — интернет-сервис помощи студентам

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

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

Кто знает КАК ЭТО ДЕЛАТЬ НА СИ???

@Sekt · 24.09.2009, 15:30

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

@natalia-82 · 24.09.2009, 15:41 **[ТС]**

как именно сформулировать чтобы искать?

@R0mm · 24.09.2009, 15:44

поищите тут...

http://www.google.com/search?client=opera&rls=ru&q=%D0%B1%D0%B 8%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%B E%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

@odip · 24.09.2009, 20:16

А как с уровнем знаний вообще - xороший, плохой или очень плохой ?
Если плохой, то не хочется расписывать

Если хороший, то алгоритм прост:
Берется рекурсивный алгоритм обхода дерева.
Как известно любое рекурсивное решение заменяется на такое же, но без рекурсии, но с использованием стека или очереди.
Поэтому там где в рекурсивном алгоритме идет вызов функции из самой себя нужно просто записать параметры вызова в стек и перейти на начало функции.
Если стек стал пуст - значит все закончено.
В самом начале нужно положить в стек узел - начало дерева.

Evg · 24.09.2009, 20:20

Сообщение от odip

А как с уровнем знаний вообще - xороший, плохой или очень плохой ?

Обход бинарного дерева без рекурсии

@Ёрик · 24.09.2009, 21:55

Вообще дерево - это связный граф.Если реализовать обход дерева с помощью поиска в ширину(там нужна очередь),то получится без рекурсии

@natalia-82 · 24.09.2009, 22:05 **[ТС]**

Это вы все правильно говорите, но мне бы код воочию увидеть, плизЗЗЗ!

@SerЁga · 24.09.2009, 22:35

Код не рекурсивного просмотра дерева которое содержит строку в каждом узле
В ф-цию передается указатель на "корень дерева"

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 · 25.09.2009, 05:24

будем считать что я опаздал

@TanT · 25.09.2009, 08:12

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

@natalia-82 · 25.09.2009, 11:28 **[ТС]**

О! Спасибо!!!!
Мне правда задавали чтобы были фунции push и pop для помещения/удаления в стек....

@Галла · 25.09.2009, 11:35

natalia-82, http://window.edu.ru/window_ca... 0&p_page=5

@natalia-82 · 25.09.2009, 11:37 **[ТС]**

и еще сказали, чтобы дерево содержало не строки, а что угодно, т.е. туда надо ввернуть указетель на функцию с void*

@natalia-82 · 07.10.2009, 16:54 **[ТС]**

А как мне написать, чтобы было тоже самое, но с функциями push() и pop()? Они у меня уже есть написанные эти пуш и поп и стек я сделала в виде связ. списка. Вроде все понятно в теории, но опыта в программировании совсем нету

И мне надо вообще-то написать 3 обхода left-root-right, right-root-left, left-right-root.

Не судите строго - я новичок!

Всем заранее спасибо за помощь!!!

@Goldcoding · 01.12.2011, 03:01

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

Новые блоги и статьи Все статьи Все блоги /
Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@natalia-82 0 / 0 / 0 Регистрация: 23.09.2009 Сообщений: 8

	НЕрекурсивный обход бинарного дерева 24.09.2009, 12:35. Показов 27207. Ответов 15 Метки деревья, структуры данных (Все метки) уважаемые программисты! нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с помощью стека. Проверить на дереве int, но в самом коде испльзовать указатели на функцию - типа что дерево состоит из чего угодно... Кто знает КАК ЭТО ДЕЛАТЬ НА СИ??? 0

@Sekt 159 / 156 / 47 Регистрация: 29.04.2009 Сообщений: 636
	24.09.2009, 15:30
	Используйте шаблон и описывайте его как одноноправленный список. хочешь примеров поисчи в гугл 0

@natalia-82 0 / 0 / 0 Регистрация: 23.09.2009 Сообщений: 8
	24.09.2009, 15:41 [ТС]
	как именно сформулировать чтобы искать? 0

@R0mm Псевдо программист 192 / 113 / 37 Регистрация: 19.09.2009 Сообщений: 303
	24.09.2009, 15:44
	поищите тут... http://www.google.com/search?client=opera&rls=ru&q=%D0%B1%D0%B 8%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%B E%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

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	24.09.2009, 20:16
	А как с уровнем знаний вообще - xороший, плохой или очень плохой ? Если плохой, то не хочется расписывать Если хороший, то алгоритм прост: Берется рекурсивный алгоритм обхода дерева. Как известно любое рекурсивное решение заменяется на такое же, но без рекурсии, но с использованием стека или очереди. Поэтому там где в рекурсивном алгоритме идет вызов функции из самой себя нужно просто записать параметры вызова в стек и перейти на начало функции. Если стек стал пуст - значит все закончено. В самом начале нужно положить в стек узел - начало дерева. 0

@Ёрик 47 / 47 / 3 Регистрация: 07.01.2009 Сообщений: 297
	24.09.2009, 21:55
	Вообще дерево - это связный граф.Если реализовать обход дерева с помощью поиска в ширину(там нужна очередь),то получится без рекурсии 0

@natalia-82 0 / 0 / 0 Регистрация: 23.09.2009 Сообщений: 8
	24.09.2009, 22:05 [ТС]
	Это вы все правильно говорите, но мне бы код воочию увидеть, плизЗЗЗ! 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	25.09.2009, 05:24
	будем считать что я опаздал 0

@natalia-82 0 / 0 / 0 Регистрация: 23.09.2009 Сообщений: 8
	25.09.2009, 11:28 [ТС]
	О! Спасибо!!!! Мне правда задавали чтобы были фунции push и pop для помещения/удаления в стек.... 0

@Галла 15 / 15 / 0 Регистрация: 22.09.2009 Сообщений: 148
	25.09.2009, 11:35
	natalia-82, http://window.edu.ru/window_ca... 0&p_page=5 0

@natalia-82 0 / 0 / 0 Регистрация: 23.09.2009 Сообщений: 8
	25.09.2009, 11:37 [ТС]
	и еще сказали, чтобы дерево содержало не строки, а что угодно, т.е. туда надо ввернуть указетель на функцию с void* 0

@natalia-82 0 / 0 / 0 Регистрация: 23.09.2009 Сообщений: 8
	07.10.2009, 16:54 [ТС]
	А как мне написать, чтобы было тоже самое, но с функциями 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
	, как пример есть программа строящая бинарное дерево и выполняющая его обход в ширину. (без рекурсии) 0