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

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

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

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

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

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
08.03.2010, 10:41 #2
Пойми сначала рекурсию, а потом и с функцией разберешься.
_Eldar_
44 / 29 / 3
Регистрация: 31.10.2009
Сообщений: 200
09.03.2010, 12:46  [ТС] #3
Рекурсивная функция, это функция которая вызыват саму себя

Добавлено через 3 часа 47 минут
Люди, добрые, помjгите разобраться

Добавлено через 22 часа 10 минут
Вот весь код
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
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <windows.h>
#include <conio.h>
 
using namespace std;
 
struct Node{
    int d;
    Node *left;
    Node *right;
};
Node *first(int d);
Node *search_insert(Node *root, int d);
void print_tree(Node *root, int l);
//----------------------------------
int main(){
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
 
    int b[] = {10, 25, 20, 6, 21, 8, 1, 30};
    Node *root = first(b[0]);
    for(int i = 1; i < 8; i++) search_insert(root, b[i]);
    cout << "+" << root->d << "\n\n"; 
    print_tree(root, 0);
    _getch();
    return 0;
}
//----------------------------------
Node *first(int d){
    Node *pv = new Node; 
    pv->d = d;
    pv->left = 0;
    pv->right = 0;
    return pv;
}
//-----------------------------------
Node *search_insert(Node *root, int d){
    Node *pv = root, *prev;
    bool found = false;
    while(pv && !found){
        prev = pv;
        if( d == pv->d) found = true;
        else if(d < pv->d) pv = pv->left;
        else pv = pv->right;
    }
    if(found) return pv;
 
    Node *pnew = new Node;
    pnew->d = d;
    pnew->left = 0;
    pnew->right = 0;
    if(d < prev->d)
        prev->left = pnew;
    else
        prev->right = pnew;
 
    return pnew;
}
//----------------------------------------
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
6
8
10
20
25 21
30

Вот как я понимаю как работает функция print_tree:
вызовы:
1) print_tree(10, 0); (лев. часть)
2) print_tree(6, 1); (лев. часть)
3)print_tree (1, 2); (лев. часть)
4)print_tree(нет левого поддерева, 3) (лев. часть)
вывод "1"
5) print_tree (нет правого поддерева, 3); (лев. часть)

все дальше не понятно как выводиться остальная часть поддерева

Добавлено через 5 минут
небольшая поправка:
5) print_tree (нет правого поддерева, 3); (прав. часть)
J_Max
Заблокирован
09.03.2010, 13:01 #4
Тоже интересует данный вопрос присоединяюсь к автору темы
Black Fregat
1381 / 1011 / 222
Регистрация: 31.05.2009
Сообщений: 4,240
09.03.2010, 13:05 #5
Уважаемый, в чем именно надо разобраться? Весь смысл рекурсии ясен из самой программы - сначала напечатаем левое поддерево, потом корень, потом правое поддерево. А если неясен сам процесс - неужели трудн натыкать печатей и получить протокол:
нажмите, чтобы увидеть
Код
8a34f4, Уровень: 0 - Вход
8a34f4, Уровень: 0 - Печать левого поддерева
8a3524, Уровень: 1 - Вход
8a3524, Уровень: 1 - Печать левого поддерева
8a3554, Уровень: 2 - Вход
8a3554, Уровень: 2 - Печать левого поддерева
0, Уровень: 3 - Вход
0, Уровень: 3- Пусто, конец рекурсии
0, Уровень: 3- Выход
8a3554, Уровень: 2 - Печать корня
      1
8a3554, Уровень: 2 - Печать правого поддерева
0, Уровень: 3 - Вход
0, Уровень: 3- Пусто, конец рекурсии
0, Уровень: 3- Выход
8a3554, Уровень: 2- Выход
8a3524, Уровень: 1 - Печать корня
   6
8a3524, Уровень: 1 - Печать правого поддерева
8a3544, Уровень: 2 - Вход
8a3544, Уровень: 2 - Печать левого поддерева
0, Уровень: 3 - Вход
0, Уровень: 3- Пусто, конец рекурсии
0, Уровень: 3- Выход
8a3544, Уровень: 2 - Печать корня
      8
8a3544, Уровень: 2 - Печать правого поддерева
0, Уровень: 3 - Вход
0, Уровень: 3- Пусто, конец рекурсии
0, Уровень: 3- Выход
8a3544, Уровень: 2- Выход
8a3524, Уровень: 1- Выход
8a34f4, Уровень: 0 - Печать корня
10
8a34f4, Уровень: 0 - Печать правого поддерева
8a3504, Уровень: 1 - Вход
8a3504, Уровень: 1 - Печать левого поддерева
8a3514, Уровень: 2 - Вход
8a3514, Уровень: 2 - Печать левого поддерева
0, Уровень: 3 - Вход
0, Уровень: 3- Пусто, конец рекурсии
0, Уровень: 3- Выход
8a3514, Уровень: 2 - Печать корня
      20
8a3514, Уровень: 2 - Печать правого поддерева
8a3534, Уровень: 3 - Вход
8a3534, Уровень: 3 - Печать левого поддерева
0, Уровень: 4 - Вход
0, Уровень: 4- Пусто, конец рекурсии
0, Уровень: 4- Выход
8a3534, Уровень: 3 - Печать корня
         21
8a3534, Уровень: 3 - Печать правого поддерева
0, Уровень: 4 - Вход
0, Уровень: 4- Пусто, конец рекурсии
0, Уровень: 4- Выход
8a3534, Уровень: 3- Выход
8a3514, Уровень: 2- Выход
8a3504, Уровень: 1 - Печать корня
   25
8a3504, Уровень: 1 - Печать правого поддерева
8a3564, Уровень: 2 - Вход
8a3564, Уровень: 2 - Печать левого поддерева
0, Уровень: 3 - Вход
0, Уровень: 3- Пусто, конец рекурсии
0, Уровень: 3- Выход
8a3564, Уровень: 2 - Печать корня
      30
8a3564, Уровень: 2 - Печать правого поддерева
0, Уровень: 3 - Вход
0, Уровень: 3- Пусто, конец рекурсии
0, Уровень: 3- Выход
8a3564, Уровень: 2- Выход
8a3504, Уровень: 1- Выход
8a34f4, Уровень: 0- Выход
kuroiryuu
316 / 300 / 23
Регистрация: 05.11.2009
Сообщений: 712
Завершенные тесты: 2
09.03.2010, 13:12 #6
а лучше преобразуйте функцию print_tree
C++
1
2
3
4
5
6
7
8
9
10
void print_tree(Node *p, int level)
{
        if(p){
                for(int i = 0; i < level; i++) cout << "--";
                cout << "Level: " << level << "; Element = "p->d << endl; // вывод корня поддерева
 
                print_tree(p->left, level + 1);         // вывод левого поддерева
                print_tree(p->right, level + 1);        // вывод левого поддерева
        }
}
_Eldar_
44 / 29 / 3
Регистрация: 31.10.2009
Сообщений: 200
09.03.2010, 13:19  [ТС] #7
для чего вообще использовать рекурсию мне не понятно , помоему кроме запутанного, но короткого кода никаких преимуществ
kuroiryuu
316 / 300 / 23
Регистрация: 05.11.2009
Сообщений: 712
Завершенные тесты: 2
09.03.2010, 13:31 #8
Цитата Сообщение от _Eldar_ Посмотреть сообщение
для чего вообще использовать рекурсию мне не понятно , помоему кроме запутанного, но короткого кода никаких преимуществ
а вы представьте, что вам необходимо вычислить что-нибудь в зависимости от разных условий, но при этом входные данные следующего расчёта это результат предыдущего, а принцип самого расчёта общий, и циклами это реализовать не получается...
_Eldar_
44 / 29 / 3
Регистрация: 31.10.2009
Сообщений: 200
09.03.2010, 13:34  [ТС] #9
kuroiryuu, можно конкретную задачку? помоему для любого рекурсивного алгоритма можно создать его нерекурсивный аналог
Black Fregat
1381 / 1011 / 222
Регистрация: 31.05.2009
Сообщений: 4,240
09.03.2010, 13:43 #10
Цитата Сообщение от _Eldar_ Посмотреть сообщение
по-моему для любого рекурсивного алгоритма можно создать его нерекурсивный аналог
Скажите, неужели рекурсию в том же обходе дерева настолько сложно понять, что Вы готовы программировать обход этого же дерева без рекурсии? Вам понадобится на каждом шаге помнить, вверх по дереву мы идем или вниз, хранить путь от вершины дерева.. На мой взгляд, сложность программы возрастет на порядок.
_Eldar_
44 / 29 / 3
Регистрация: 31.10.2009
Сообщений: 200
09.03.2010, 14:02  [ТС] #11
не знаю, может быть с опытом будет проще понимать рекурсию, у нее все равно есть главный недосток - все параметры функции при каждом вызове копируются в стек, к-ый может переполниться
kuroiryuu
316 / 300 / 23
Регистрация: 05.11.2009
Сообщений: 712
Завершенные тесты: 2
09.03.2010, 14:14 #12
Цитата Сообщение от _Eldar_ Посмотреть сообщение
kuroiryuu, можно конкретную задачку? помоему для любого рекурсивного алгоритма можно создать его нерекурсивный аналог
например, попробуйте вывести на экран все папки, которые есть на заданном диске, включая вложенные (файлы не обязательно), но без использования рекурсии
а потом тоже самое, но с рекурсией
easybudda
Модератор
Эксперт CЭксперт С++
9530 / 5523 / 932
Регистрация: 25.07.2009
Сообщений: 10,608
09.03.2010, 18:20 #13
_Eldar_, обошлось без рекурсии, но вроде и дерево создаётся, и печатается... Короче вот:
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdlib>
 
class Node {
public:
    Node() : _left(NULL), _right(NULL), _val(0) {}
    Node(int v) : _left(NULL), _right(NULL), _val(v) {}
    Node(int v, Node *n) {
        if ( v < n->val() ){
            while ( n->val() > v && n->left() != NULL )
                n = n->left();       
        }
        else if ( v > n->val() ){
            while ( n->val() < v && n->right() != NULL)
                n = n->right();
        }
        if ( v == n->val() ){
            std::cerr << "Doubling value (" << v << ")!" << std::endl;
            exit(1);
        }
        else if ( v < n->val() ){
            _right = n;
            _left = n->left();
            n->left(this);
            if ( _left )
                _left->right(this);
        }
        else {
            _left = n;
            _right = n->right();
            n->right(this);
            if ( _right )
                _right->left(this);
        }
        _val = v;
    }
    int val() const { return _val; }
    void val(int v) { _val = v; }
    Node *left() const { return _left; }
    void left(Node *n) { _left = n; }
    Node *right() const { return _right; }
    void right(Node *n) { _right = n; }
    Node *first() const {
        const Node *f = this;
        while ( f->left() != NULL )
            f = f->left();
        return (Node*)f;
    }
    Node *last() const {
        const Node *l = this;
        while ( l->right() != NULL )
            l = l->right();
        return (Node*)l;
    }
private:
    Node *_left;
    Node *_right;
    int _val;
};
 
void printTree(Node *n){
    n = n->first();
    while ( n ){
        std::cout << n->val() << ' ';
        n = n->right();
    }
}
 
void killTree(Node *n){
    Node *t;
    n = n->first();
    while ( n ){
        t = n->right();
        delete n;
        n = t;
    }
}
 
int main(){
    const int values = 10;
    int arr[values] = { 2, 1, 3, 6, 4, 9, 7, 5, 0, 8 }, i;
    Node *n = new Node(arr[0]);
    for ( i = 1; i < values; ++i ){
        n = new Node(arr[i], n);
    }
 
    printTree(n);
    killTree(n);
    std::cout << std::endl;
    return 0;
}
_Eldar_
44 / 29 / 3
Регистрация: 31.10.2009
Сообщений: 200
10.03.2010, 00:57  [ТС] #14
Спасибо всем отозвавшимся))
kuroiryuu, я пока такую задачу точно не решу, я только консольные приложения пишу, да я понимаю что запись будет короче с рекурсией, с примером сталкивался (быстрая сортировка массива), я имел в виду что любой рекурсивный алгоритм можно преписать нерекурсивным.
easybudda, спасибо, но до изучения классов я еще не дошел
Black Fregat
1381 / 1011 / 222
Регистрация: 31.05.2009
Сообщений: 4,240
10.03.2010, 08:21 #15
На мой взгляд, Вы делаете определенную подмену понятий. Вы всё время делаете упор на то, что рекурсивный код получается более короткий. Но бывает такая краткость, которая только запутывает. На мой взгляд, тут наоборот, рекурсивный код получается более логичный и понятный.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.03.2010, 08:21
Привет! Вот еще темы с ответами:

НЕрекурсивный обход бинарного дерева - 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...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.03.2010, 08:21
Ответ Создать тему
Опции темы

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