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

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

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

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

08.03.2010, 10:40. Просмотров 7981. Ответов 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;
};
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2010, 10:40
Здравствуйте! Я подобрал для вас темы с ответами на вопрос "Рекурсивная функция" (Обход бинарного дерева) (C++):

Вывод бинарного дерева на экран в виде "дерева" - C++
основная задача: подсчет количества листьев. проблема: при просмотре хочу выводить бин. дерево, в красивом виде, возможно использование...

Разница между понятиями "Обход в прямом направлении" и "Итерационный прямой обход" - C++
Ребятаа, обьясните чем различается: Обход в прямом направлении и Итерационный прямой обход Добавлено через 10 минут НароооД,...

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

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

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

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

31
kuroiryuu
317 / 301 / 23
Регистрация: 05.11.2009
Сообщений: 712
Завершенные тесты: 2
10.03.2010, 09:37 #16
Цитата Сообщение от Black Fregat Посмотреть сообщение
рекурсивный код получается более логичный и понятный.
согласен с этим, не надо придумывать велосипед, для решения задач.
там где уместны циклы используй циклы, а где рекурсии - рекурсии.
0
Yurii_74
paladin
280 / 180 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 10:03 #17
Пример, когда рекурсия не подойдет: нарисуйте какой-нибудь фрактал с глубиной в 10^n. Для определенных n "Stack overflow error" обеспечен.
1
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
10.03.2010, 11:16 #18
Данный алгоритм, можно организовать и без рекурсии с помощью дополнительной динамической структуры допустим: стек: так как стек позволяет запоминать направления движения по графу.
С рекурсией присутствует стек: так сказать аппаратный(на уровне компилятора),
он то и позволят запоминать шаги, для дальнейшего продвижения по графу.
0
Black Fregat
1392 / 1023 / 228
Регистрация: 31.05.2009
Сообщений: 4,275
10.03.2010, 11:25 #19
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Пример, когда рекурсия не подойдет: нарисуйте какой-нибудь фрактал с глубиной в 10^n. Для определенных n "Stack overflow error" обеспечен.
Извините, но не могу согласиться.

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

Во-вторых, что нам мешает сделать стек поглубже, а стековых переменных - поменьше? Пару гигов на стек - и золотой ключик у нас в кармане. А когда вычисления подходят к границе ресурсов, тут уж поневоле приходится усложнять алгоритмы. Это не только с рекурсией, простая сортировка ведет себя не лучше при возрастании объемов сортируемой информации.
0
Genius Ignat
1236 / 774 / 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);
}
2
Yurii_74
paladin
280 / 180 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 11:54 #21
Ну что поделать. Рекурсия в том виде, в котором она реализована (через стек) - не очень замечательная вещь. Динамическое выделение памяти - достаточно простое решение, не требующее колоссальных затрат времени и сил.
Цитата Сообщение от Black Fregat Посмотреть сообщение
Вполне можно представить себе компилятор, убирающий лишние стековые итерации.
Машина не должна быть умнее человека. А то так 2+2 не сможем посчитать однажды. Хотя бы принципы того, как это делается, понимать должны.
Цитата Сообщение от Black Fregat Посмотреть сообщение
Пару гигов на стек
А если у человека не будет этой пары? При нормальном выделении памяти мы можем дойти до того максимума, который позволен на данной конфигурации и вернуться из всего этого, выдав сообщение о том, что смогли дойти дотуда-то.
1
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
10.03.2010, 12:15 #22
Сообщение от Black Fregat
Пару гигов на стек
Погорячился.


Я где то на форуме видел: создавал кто то массив в 100 000 элементов я точно не помню,
может больше( на один нуль), и компилятор писал Stack Overlow.
Тип элементов был int, пару гигов этот массив не весит точно.
1
J_Max
Заблокирован
10.03.2010, 12:36 #23
Всем спасибо, один вопрос, что лучше использовать:
То что предложил Genius Ignat или использовать рекурсию, желательно с убедительными аргументами.
0
Yurii_74
paladin
280 / 180 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 12:42 #24
Если глубина рекурсии мала - ее и использовать (для нескольких интов, передаваемых в рекурсивную функцию глубина порядка 10^3 - 10^4, не больше). В противном случае реализовывать хранение промежуточных значений в динамическом стеке.
2
Black Fregat
1392 / 1023 / 228
Регистрация: 31.05.2009
Сообщений: 4,275
10.03.2010, 13:15 #25
Цитата Сообщение от J_Max Посмотреть сообщение
Всем спасибо, один вопрос, что лучше использовать:
То что предложил Genius Ignat или использовать рекурсию, желательно с убедительными аргументами.
А тут, как всегда, выигрыш одного за счет другого. Рекурсия дает более читабельный код, он быстрее пишется и легче сопровождается. Но он, безусловно, не оптимален, как по расходованию ресурсов, так и по производительности. Если есть необходимость оптимизации по этим параметрам, то раскрывать рекурсию надо однозначно. Причем, вполне возможно, даже глубже, чем сделал Genius Ignat - у него, по сути, та же рекурсия, только замаскированная. Для остальных задач вопрос упирается в стиль программирования, что уже весьма субъективно. И уж однозначно, на мой взгляд, не стоит бороться с рекурсией при острой нехватке времени на разработку.
0
Genius Ignat
1236 / 774 / 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;
}
Как смог так объяснил.
4
Black Fregat
1392 / 1023 / 228
Регистрация: 31.05.2009
Сообщений: 4,275
10.03.2010, 14:10 #27
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Погорячился. Я где то на форуме видел: создавал кто то массив в 100 000 элементов я точно не помню, может больше( на один нуль), и компилятор писал Stack Overlow.
Тип элементов был int, пару гигов этот массив не весит точно.
Размер стека настраивается.
Значение минимального размера стека может задаваться целым числом в диапазоне между1024 и 2147483647. Значение максимального размера стека должно быть не менее минимального размера и не более 2147483647.
2
Genius Ignat
1236 / 774 / 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;
}
2
Yurii_74
paladin
280 / 180 / 3
Регистрация: 25.02.2009
Сообщений: 592
10.03.2010, 14:21 #29
Цитата Сообщение от Black Fregat Посмотреть сообщение
Размер стека настраивается.
Но память-то под него выделяется при запуске? Оно того стоит? По моему скромному мнению лучше подучить немного прогеров, чем писать настолько неоптимальные решения.
2
Black Fregat
1392 / 1023 / 228
Регистрация: 31.05.2009
Сообщений: 4,275
10.03.2010, 14:59 #30
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Но память-то под него выделяется при запуске? Оно того стоит? По моему скромному мнению лучше подучить немного прогеров, чем писать настолько неоптимальные решения.
Было время, когда и отдельные байты экономили. Что-то обязательно приносится в жертву.
3
10.03.2010, 14:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.03.2010, 14:59
Привет! Вот еще темы с ответами:

НЕрекурсивный обход бинарного дерева - C++
уважаемые программисты! нужно написать алгоритм обхода бинарного дерева без использования рекурсии, а с помощью стека. Проверить на...

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

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

У меня класс B в классе A, а в классе B рекурсивная функция переопределения оператора "()", как её вызвать, не создавая явно объект класса B? - C++
#include &lt;windows.h&gt; #include &lt;iostream&gt; using namespace std; //Вот главный класс class A{ public: A (){}; class...


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

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

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