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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 58, средняя оценка - 4.71
_Eldar_
44 / 29 / 3
Регистрация: 31.10.2009
Сообщений: 200
#1

"Рекурсивная функция" (Обход бинарного дерева) - C++

08.03.2010, 10:40. Просмотров 7797. Ответов 31
Метки нет (Все метки)

Привет всем, встретился с такой рекурсивной ф-ей, которая обходит бинарное дерево и выводит его на экран. Не могу понять как она работает
C++
1
2
3
4
5
6
7
8
void print_tree(Node *p, int level){
    if(p){
        print_tree(p->left, level + 1);     // вывод левого поддерева
        for(int i = 0; i < level; i++) cout << "   ";
        cout << p->d << endl;               // вывод корня поддерева
        print_tree(p->right, level + 1);    // вывод левого поддерева
    }
}
первый параметр это указатель на элемент дерева, а второй - уровень на катором находиться узел.
Объясните пожалуйста принцип работы такой функции. Заранее благодарен )

Добавлено через 1 минуту
вот сама структура:
C++
1
2
3
4
5
struct Node{
    int d;
    Node *left;
    Node *right;
};
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kuroiryuu
316 / 300 / 23
Регистрация: 05.11.2009
Сообщений: 712
Завершенные тесты: 2
10.03.2010, 09:37     "Рекурсивная функция" (Обход бинарного дерева) #16
Цитата Сообщение от Black Fregat Посмотреть сообщение
рекурсивный код получается более логичный и понятный.
согласен с этим, не надо придумывать велосипед, для решения задач.
там где уместны циклы используй циклы, а где рекурсии - рекурсии.
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 10:03     "Рекурсивная функция" (Обход бинарного дерева) #17
Пример, когда рекурсия не подойдет: нарисуйте какой-нибудь фрактал с глубиной в 10^n. Для определенных n "Stack overflow error" обеспечен.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
10.03.2010, 11:16     "Рекурсивная функция" (Обход бинарного дерева) #18
Данный алгоритм, можно организовать и без рекурсии с помощью дополнительной динамической структуры допустим: стек: так как стек позволяет запоминать направления движения по графу.
С рекурсией присутствует стек: так сказать аппаратный(на уровне компилятора),
он то и позволят запоминать шаги, для дальнейшего продвижения по графу.
Black Fregat
1381 / 1011 / 222
Регистрация: 31.05.2009
Сообщений: 4,240
10.03.2010, 11:25     "Рекурсивная функция" (Обход бинарного дерева) #19
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Пример, когда рекурсия не подойдет: нарисуйте какой-нибудь фрактал с глубиной в 10^n. Для определенных n "Stack overflow error" обеспечен.
Извините, но не могу согласиться.

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

Во-вторых, что нам мешает сделать стек поглубже, а стековых переменных - поменьше? Пару гигов на стек - и золотой ключик у нас в кармане. А когда вычисления подходят к границе ресурсов, тут уж поневоле приходится усложнять алгоритмы. Это не только с рекурсией, простая сортировка ведет себя не лучше при возрастании объемов сортируемой информации.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
10.03.2010, 11:51     "Рекурсивная функция" (Обход бинарного дерева) #20
Вывод без рекурсии общий принцип: на основе ДСД: стека.
C++
1
2
3
4
5
6
7
8
Stack * top = NULL;
push(&top,r);
while(top){
r = pop(&top);
cout<<r->d;
if(r->right)push(&top,r->right);
if(r->left)push(&top,r->legt);
}
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 11:54     "Рекурсивная функция" (Обход бинарного дерева) #21
Ну что поделать. Рекурсия в том виде, в котором она реализована (через стек) - не очень замечательная вещь. Динамическое выделение памяти - достаточно простое решение, не требующее колоссальных затрат времени и сил.
Цитата Сообщение от Black Fregat Посмотреть сообщение
Вполне можно представить себе компилятор, убирающий лишние стековые итерации.
Машина не должна быть умнее человека. А то так 2+2 не сможем посчитать однажды. Хотя бы принципы того, как это делается, понимать должны.
Цитата Сообщение от Black Fregat Посмотреть сообщение
Пару гигов на стек
А если у человека не будет этой пары? При нормальном выделении памяти мы можем дойти до того максимума, который позволен на данной конфигурации и вернуться из всего этого, выдав сообщение о том, что смогли дойти дотуда-то.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
10.03.2010, 12:15     "Рекурсивная функция" (Обход бинарного дерева) #22
Сообщение от Black Fregat
Пару гигов на стек
Погорячился.


Я где то на форуме видел: создавал кто то массив в 100 000 элементов я точно не помню,
может больше( на один нуль), и компилятор писал Stack Overlow.
Тип элементов был int, пару гигов этот массив не весит точно.
J_Max
Заблокирован
10.03.2010, 12:36     "Рекурсивная функция" (Обход бинарного дерева) #23
Всем спасибо, один вопрос, что лучше использовать:
То что предложил Genius Ignat или использовать рекурсию, желательно с убедительными аргументами.
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 12:42     "Рекурсивная функция" (Обход бинарного дерева) #24
Если глубина рекурсии мала - ее и использовать (для нескольких интов, передаваемых в рекурсивную функцию глубина порядка 10^3 - 10^4, не больше). В противном случае реализовывать хранение промежуточных значений в динамическом стеке.
Black Fregat
1381 / 1011 / 222
Регистрация: 31.05.2009
Сообщений: 4,240
10.03.2010, 13:15     "Рекурсивная функция" (Обход бинарного дерева) #25
Цитата Сообщение от J_Max Посмотреть сообщение
Всем спасибо, один вопрос, что лучше использовать:
То что предложил Genius Ignat или использовать рекурсию, желательно с убедительными аргументами.
А тут, как всегда, выигрыш одного за счет другого. Рекурсия дает более читабельный код, он быстрее пишется и легче сопровождается. Но он, безусловно, не оптимален, как по расходованию ресурсов, так и по производительности. Если есть необходимость оптимизации по этим параметрам, то раскрывать рекурсию надо однозначно. Причем, вполне возможно, даже глубже, чем сделал Genius Ignat - у него, по сути, та же рекурсия, только замаскированная. Для остальных задач вопрос упирается в стиль программирования, что уже весьма субъективно. И уж однозначно, на мой взгляд, не стоит бороться с рекурсией при острой нехватке времени на разработку.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
10.03.2010, 14:05     "Рекурсивная функция" (Обход бинарного дерева) #26
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот думал думал, как автору пояснить что такое рекурсия, и сделал
функцию разворота массива: здесь явно показана работа со стеком,
пример факториала я посчитал, что лучше его не показывать.
//--------------------------------------------------------------------
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
//Пример рекурсивной функций, разворота массива: работа с аппаратным стеком. 
#include <iostream.h>
void reverse(int *mas,int val,int iter, int otcat_iter);
 
int main(){
 
const int SIZE = 10; 
 
int massive[SIZE] = {1,2,3,4,5,6,7,8,9,0};
 
reverse(massive,massive[0],1,SIZE-1);
 
for(int i=0;i<SIZE;i++)cout<<massive[i];
 
cout<<'\n';
return 0;
}
void reverse(int *mas, int val, int iter, int otcat_iter){
//Точка 1.  
    //----------------------------------------------------
    //Ветвь возрата завершает последнюю вызванную функцию,
    if(otcat_iter==0){
    mas[otcat_iter]=val;
    return;
    }
    //После этого действия: действия будут переходить в точку 2, 
    //----------------------------------------------------
 
reverse(mas, mas[0+iter],iter+1,otcat_iter-1);
 
//Точка 2.
//Это место: есть продолжение дейсвия каждой вызванной функцию,
//после возрата из очередной завершившейся функции.
mas[otcat_iter]=val;  /*этот код будет повторяться: пропорциоанльно количеству вызовов функций-1(одну), значения val и otcat_it
Будут меняться так как мы будет работать с параметрами разных функций.
Да и другие параметры будут меняться.
В эту точку передаётся управления как только очередная вызванная функция завершается.
  */
//-----------------------------------------------------------------------------------
}
Надеюсь мой труд не напрасен.

Добавлено через 28 минут
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
51
52
53
54
55
56
57
//Более подробное исследование рекурсии: сравнение с аналогом не рекурсией.
void f(int i){
if(i>=5)return;    
f(i+1);    
}
 
/*Поведение  рекурсивной функции  f, можно смоделировать с помощью нескольких функций, но реализация ограничена количеством функции, а рекурсия не зависит от количества функций
*/
void f1(int i);          //эта функция вызывается в main
void f2(int i);          //эта функция вызывается в f1           
void f3(int i);          //эта функция вызывается в f2
void f4(int i);          //эта функция вызывается в f3
void f5(int i);          //эта функция вызывается в f4
void f6(int i);          //эта функция вызывается в f5
//--------------------------------------------------------------------------------------------------------------------------
 
//эта функция вызывается в main
void f1(int i){
if(i>=5)return;
f2(i+1);            //вызываем f2
//После возврата из f2 управление попадёт сюда
 
}
//эта функция вызывается в f1
void f2(int i){
if(i>=5)return;
f3(i+1);            //вызываем f3
//После возврата из f3 управление попадёт сюда
}
//эта функция вызывается в f2
void f3(int i){
if(i>=5)return;
f4(i+1);            //вызываем f4
//После возврата из f4 управление попадёт сюда
}
//эта функция вызывается в f3
void f4(int i){
if(i>=5)return;
f5(i+1);            //вызываем f5
//После возврата из f5 управление попадёт сюда
}
//эта функция вызывается в f4
void f5(int i){
if(i>=5)return ;
f6(i+1);            //вызываем f6
//После возврата из f6 управление попадёт сюда
}
void f6(int i){
if(i>=5)return;
//Эта уже закон, если не указать return вызовы будут бесконечны(пока не переполнится стек), 
//но у нас не рекурсия.
 
}
int main(){
f1(0);
return 0;
}
Как смог так объяснил.
Black Fregat
1381 / 1011 / 222
Регистрация: 31.05.2009
Сообщений: 4,240
10.03.2010, 14:10     "Рекурсивная функция" (Обход бинарного дерева) #27
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Погорячился. Я где то на форуме видел: создавал кто то массив в 100 000 элементов я точно не помню, может больше( на один нуль), и компилятор писал Stack Overlow.
Тип элементов был int, пару гигов этот массив не весит точно.
Размер стека настраивается.
Значение минимального размера стека может задаваться целым числом в диапазоне между1024 и 2147483647. Значение максимального размера стека должно быть не менее минимального размера и не более 2147483647.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
10.03.2010, 14:18     "Рекурсивная функция" (Обход бинарного дерева) #28
А вот ещё пример вывод нескольких значений в обратном поступлению
порядке, за счет стека и параметров.

C++
1
2
3
4
5
6
7
8
void f(int i){
if(i>=10){
cout<<i;
return;
}
f(i+1);
cout<<i;
}
Yurii_74
paladin
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 14:21     "Рекурсивная функция" (Обход бинарного дерева) #29
Цитата Сообщение от Black Fregat Посмотреть сообщение
Размер стека настраивается.
Но память-то под него выделяется при запуске? Оно того стоит? По моему скромному мнению лучше подучить немного прогеров, чем писать настолько неоптимальные решения.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.03.2010, 14:59     "Рекурсивная функция" (Обход бинарного дерева)
Еще ссылки по теме:
C++ Обход бинарного дерева без рекурсии
У меня класс B в классе A, а в классе B рекурсивная функция переопределения оператора "()", как её вызвать, не создавая явно объект класса B? C++
C++ Бинарное дерево. Обход бинарного дерева (симметрический, прямой и обратный)
Функция вывода листьев бинарного дерева C++
C++ Почему не работает функция std::regex_replace(temp,"amp;","");

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

Или воспользуйтесь поиском по форуму:
Black Fregat
1381 / 1011 / 222
Регистрация: 31.05.2009
Сообщений: 4,240
10.03.2010, 14:59     "Рекурсивная функция" (Обход бинарного дерева) #30
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Но память-то под него выделяется при запуске? Оно того стоит? По моему скромному мнению лучше подучить немного прогеров, чем писать настолько неоптимальные решения.
Было время, когда и отдельные байты экономили. Что-то обязательно приносится в жертву.
Yandex
Объявления
10.03.2010, 14:59     "Рекурсивная функция" (Обход бинарного дерева)
Ответ Создать тему
Опции темы

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