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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 58, средняя оценка - 4.71
_Eldar_
 Аватар для _Eldar_
44 / 29 / 3
Регистрация: 31.10.2009
Сообщений: 200
08.03.2010, 10:40     "Рекурсивная функция" (Обход бинарного дерева) #1
Привет всем, встретился с такой рекурсивной ф-ей, которая обходит бинарное дерево и выводит его на экран. Не могу понять как она работает
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;
};
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2010, 10:40     "Рекурсивная функция" (Обход бинарного дерева)
Посмотрите здесь:

НЕрекурсивный обход бинарного дерева C++
C++ обход бинарного дерева без рекурсии
C++ Бинарное дерево. Обход бинарного дерева (симметрический, прямой и обратный)
C++ Обход бинарного дерева
У меня класс B в классе A, а в классе B рекурсивная функция переопределения оператора "()", как её вызвать, не создавая явно объект класса B? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 11:54     "Рекурсивная функция" (Обход бинарного дерева) #21
Ну что поделать. Рекурсия в том виде, в котором она реализована (через стек) - не очень замечательная вещь. Динамическое выделение памяти - достаточно простое решение, не требующее колоссальных затрат времени и сил.
Цитата Сообщение от Black Fregat Посмотреть сообщение
Вполне можно представить себе компилятор, убирающий лишние стековые итерации.
Машина не должна быть умнее человека. А то так 2+2 не сможем посчитать однажды. Хотя бы принципы того, как это делается, понимать должны.
Цитата Сообщение от Black Fregat Посмотреть сообщение
Пару гигов на стек
А если у человека не будет этой пары? При нормальном выделении памяти мы можем дойти до того максимума, который позволен на данной конфигурации и вернуться из всего этого, выдав сообщение о том, что смогли дойти дотуда-то.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Genius Ignat
1233 / 771 / 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
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 12:42     "Рекурсивная функция" (Обход бинарного дерева) #24
Если глубина рекурсии мала - ее и использовать (для нескольких интов, передаваемых в рекурсивную функцию глубина порядка 10^3 - 10^4, не больше). В противном случае реализовывать хранение промежуточных значений в динамическом стеке.
Black Fregat
 Аватар для Black Fregat
1353 / 983 / 215
Регистрация: 31.05.2009
Сообщений: 4,093
10.03.2010, 13:15     "Рекурсивная функция" (Обход бинарного дерева) #25
Цитата Сообщение от J_Max Посмотреть сообщение
Всем спасибо, один вопрос, что лучше использовать:
То что предложил Genius Ignat или использовать рекурсию, желательно с убедительными аргументами.
А тут, как всегда, выигрыш одного за счет другого. Рекурсия дает более читабельный код, он быстрее пишется и легче сопровождается. Но он, безусловно, не оптимален, как по расходованию ресурсов, так и по производительности. Если есть необходимость оптимизации по этим параметрам, то раскрывать рекурсию надо однозначно. Причем, вполне возможно, даже глубже, чем сделал Genius Ignat - у него, по сути, та же рекурсия, только замаскированная. Для остальных задач вопрос упирается в стиль программирования, что уже весьма субъективно. И уж однозначно, на мой взгляд, не стоит бороться с рекурсией при острой нехватке времени на разработку.
Genius Ignat
1233 / 771 / 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
 Аватар для Black Fregat
1353 / 983 / 215
Регистрация: 31.05.2009
Сообщений: 4,093
10.03.2010, 14:10     "Рекурсивная функция" (Обход бинарного дерева) #27
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Погорячился. Я где то на форуме видел: создавал кто то массив в 100 000 элементов я точно не помню, может больше( на один нуль), и компилятор писал Stack Overlow.
Тип элементов был int, пару гигов этот массив не весит точно.
Размер стека настраивается.
Значение минимального размера стека может задаваться целым числом в диапазоне между1024 и 2147483647. Значение максимального размера стека должно быть не менее минимального размера и не более 2147483647.
Genius Ignat
1233 / 771 / 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
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 14:21     "Рекурсивная функция" (Обход бинарного дерева) #29
Цитата Сообщение от Black Fregat Посмотреть сообщение
Размер стека настраивается.
Но память-то под него выделяется при запуске? Оно того стоит? По моему скромному мнению лучше подучить немного прогеров, чем писать настолько неоптимальные решения.
Black Fregat
 Аватар для Black Fregat
1353 / 983 / 215
Регистрация: 31.05.2009
Сообщений: 4,093
10.03.2010, 14:59     "Рекурсивная функция" (Обход бинарного дерева) #30
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Но память-то под него выделяется при запуске? Оно того стоит? По моему скромному мнению лучше подучить немного прогеров, чем писать настолько неоптимальные решения.
Было время, когда и отдельные байты экономили. Что-то обязательно приносится в жертву.
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
10.03.2010, 15:28     "Рекурсивная функция" (Обход бинарного дерева) #31
Так же используется как я её называю завершающая рекурсия которая предназначения для
обмена с функциями через возвращающее значение, и не требующая работы с параметрами
предыдущей вызванной функций после завершения очередной функции, то есть откат к параметрам назад можно не использовать.
Такой тип функций используются допустим в поиске с включением в дереве
или просто в поиске в дереве.

Пример рекурсивная функция, которая не использует "откатанные назад параметры после завершения очередной самой себя функции".

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
//Поиск минимального значения в массиве.
#include <stdio.h>
#include <conio.h>
 
#define size 10
int find_min(int *mas, int size_t, int iter , int E_min );
 
 
int main(){
 
int massive[size] = {3,2,3,9,5,6,7,-5,9,-6};
int i;
for(i=0;i<size;i++)printf(" %d",massive[i]);
printf("\n");
 
printf("\n");
printf("min %d ",find_min(massive,size,0,massive[0]));
printf("\n");
 
 
getch();
return 0;
 
 
}
 
int find_min(int *mas,int size_t, int iter, int E_min){
if(mas[iter]<E_min){
    E_min=mas[iter];
}
 
if(iter==size_t-1)return E_min;
//(если наступило условие)делаются возвраты, которые переносят значение.
return find_min(mas,size_t,iter+1,E_min); 
 
}
//Пример рекурсивной функции поиска в дереве:
//Поиск узла рекурсией----------
C++
1
2
3
4
5
6
7
8
9
10
Node *FindR(Node *root , int x){
   //Пока не дойдём до конечной точки или не пока не найден узел------------
   if(root){ 
       
   if(x==root->dan) return root;                        //нашли---------------------
   else if (x<root->dan) return FindR(root->left,x);    //переходим в левое поддерево
   else return FindR(root->right,x);                    //переходим в правое поддерево
   } 
   else return 0;
}
Добавлено через 8 минут
inline перед рекурсивными функциями можно не ставить, так как inline вызовов не будет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.03.2010, 15:54     "Рекурсивная функция" (Обход бинарного дерева)
Еще ссылки по теме:

C++ Вывод бинарного дерева на экран в виде "дерева"
C++ обход бинарного дерева
Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" C++

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

Или воспользуйтесь поиском по форуму:
J_Max
Заблокирован
10.03.2010, 15:54     "Рекурсивная функция" (Обход бинарного дерева) #32
Хороший сайт, и объясняют понятнее и лучше чем в учебнике,
В учебнике буквально три строчки о рекурсии, и примера кроме факториала больше нет, вот так.

Ещё раз спасибо всем, узнал много нового.
Yandex
Объявления
10.03.2010, 15:54     "Рекурсивная функция" (Обход бинарного дерева)
Ответ Создать тему
Опции темы

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