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

Рекурсивные функции в классе - C++

Восстановить пароль Регистрация
 
vruleb
0 / 0 / 0
Регистрация: 26.05.2012
Сообщений: 17
12.11.2013, 11:49     Рекурсивные функции в классе #1
Я написал рабочий класс для работы с бинарным деревом поиска и в нём имеется много рекурсивных методов (по заданию). Из-за этого эти функции приходится вызывать через другие функции. Можно ли всё это реализовать более "элегантно", или же это единственный выход?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.11.2013, 11:49     Рекурсивные функции в классе
Посмотрите здесь:

C++ рекурсивные функции
рекурсивные функции C++
C++ рекурсивные функции
C++ Рекурсивные функции
Рекурсивные функции C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.11.2013, 12:08     Рекурсивные функции в классе #2
vruleb, Хвостовую рекурсию можно использовать. Можно и итеративно (только зачем?). И чем впринципе не устраивает рекурсия в данном контексте?
vruleb
0 / 0 / 0
Регистрация: 26.05.2012
Сообщений: 17
12.11.2013, 12:21  [ТС]     Рекурсивные функции в классе #3
Да в принципе устраивает, просто захотелось убрать лишние полупустые функции. Также пришла в голову мысль перегрузить эти функции.
Вот сам класс:
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
template <class T1, class T2>
class Tree {
private:
    class Node {
    public:
        T1 _value;
        T2 key;
        Node *left;
        Node *right;
    public:
        Node()
        {
            key = NULL; _value = NULL; left = NULL; right = NULL;
        }
        Node(T1 val, T2 k)
        {
            key = k; _value = val; left = NULL; right = NULL;
        }
        ~Node()
        {
            left = NULL; right = NULL;
        }
        friend ostream& operator << (ostream &stream, Node &obj)
        {
            stream << obj.key << " - " << obj._value;
            return stream;
        }
        void Delete()
        {
            if (left)
                left->~Node();
            if (right)
                right->~Node();
            if (left) {
                delete left; left = NULL;
            }
            if (right) {
                delete right; right = NULL;
            }
            _value = NULL;
        }
    };
    Node *head;
private: // приватные рекурсивные функции
    // функция обхода дерева с подсчетом количества узлов
    void L_R_t(Node *t, int &p)
    {
        if (t == 0) return;
        L_R_t(t->left, p);
        L_R_t(t->right, p);
        p++;
    }
    // функция обхода дерева с выводом содержимого узлов на экран
    void L_R_t(Node *t)
    {
        if (t == 0) return;
        cout << *t << endl;
        L_R_t(t->left);
        L_R_t(t->right);
    }
    // поиск узла с заданным ключом
    Node *BST_Search(Node *t, T2 k)
    {
        if (t == 0)
            return t;
        if (k == t->key)
            return t;
        if (k < t->key)
            BST_Search(t->left, k);
        else
            BST_Search(t->right, k);
    }
    // удаление узла с заданным ключом
    Node *BST_Delete(Node *t, T2 k)
    {
        if (t == NULL)
            return t;
        if (k < t->key) {
            t->left = BST_Delete(t->left, k);
            return t;
        }
        if (k > t->key) {
            t->right = BST_Delete(t->right, k);
            return t;
        }
        if (t->left == NULL && t->right == NULL) {
            delete t;
            return NULL;
        }
        if (t->left == NULL) {
            Node *l = t->right;
            delete t;
            return l;
        }
        if (t->right == NULL) {
            Node *x = t->left;
            delete t;
            return x;
        }
        t->right = Del(t->right, t);
        return t;
    }
    
    Node *Del(Node *t, Node *t0)
    {
        if (t->left != NULL) {
            t->left = Del(t->left, t0);
            return t;
        }
        t0->key = t->key;
        t0->_value = t->_value;
        Node *x = t->right;
        delete t;
        return x;
    }
    // поиск для заданного ключа предыдущего по значению ключа в дереве
    Node *BST_SearchPrev(Node *t, T2 k)
    {
        if (t == 0)
            return t;
        if (t->right->key == k)
            return t;
        if (k < t->key)
            BST_SearchPrev(t->left, k);
        else
            BST_SearchPrev(t->right, k);
    }
    // включение в дерево нового узла с заданным ключом и данными
    Node *BST_Add(Node *t, T1 val, T2 k)
    {
        if (head == NULL) {
            head = new Node(val, k);
            return head;
        }
        if (t == NULL) {
            t = new Node(val, k);
            return t;
        }
        if (k == t->key)
            return t;
        if (k < t->key)
            t->left = BST_Add(t->left, val, k);
        else
            t->right = BST_Add(t->right, val, k);
        return t;
    }
    // вывод структуры дерева на экран
    void BST_Print(Node *t, int n)
    {
        if (t != NULL) {
            BST_Print(t->right, n + 1);
            for (int i = 0; i < n; i++)
                cout << "  ";
            cout << *t << endl;
            BST_Print(t->left, n + 1);
        }
    }
public:
    Tree()
    {
        head = NULL;
    }
    ~Tree()
    {
        head->Delete();
        delete head;
    }
    // опрос размера дерева
    int SizeTree()
    {
        int p = 0;
        L_R_t(head, p);
        return p;
    }
    // очистка структуры дерева
    void DeleteTree()
    {
        head->Delete();
    }
    // проверка дерева на пустоту
    bool Check()
    {
        if (head == NULL) return false;
        else return true;
    }
    // поиск данных с заданным ключом
    void Search(T2 k)
    {
        Node *h = BST_Search(head, k);
        if (h) cout << *h;
    }
    // поиск для заданного ключа предыдущего по значению ключа в дереве
    void SearchPrev(T2 k)
    {
        Node *h = BST_SearchPrev(head, k);
        if (h) cout << *h;
    }
    // удаление узла с заданным ключом
    void DeleleNode(T2 k)
    {
        BST_Delete(head, k);
    }
    // вывод структуры дерева на экран
    void Print()
    {
        BST_Print(head, 0);
    }
    // вывод ключей в порядке обхода
    void PrintL_R_t()
    {
        L_R_t(head);
    }
    // включение нового узла
    void Add(T1 val, T2 k)
    {
        BST_Add(head, val, k);
    }
};
ShadowFirst
54 / 47 / 1
Регистрация: 31.10.2013
Сообщений: 161
12.11.2013, 12:45     Рекурсивные функции в классе #4
Может я чего не понимаю но почему основные ваши функции находятся в privet, а для их вызова используются промежуточные функции. В чем проблема сразу их сделать public?

А если по теме то например от одной функции можно точно избавиться, которая вам выдает количество элементов в дереве, вернее не совсем избавиться а просто каждый раз не обходить это дерево для того что бы узнать количество элементов, заменив на статическую переменную, которая будет прибавляться на 1 при добавлении элемента и уменьшаться при удалении.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.11.2013, 12:49     Рекурсивные функции в классе #5
Явный вызов деструкторов точно следует убрать. delete вызовет деструктор сам.
vruleb
0 / 0 / 0
Регистрация: 26.05.2012
Сообщений: 17
12.11.2013, 13:21  [ТС]     Рекурсивные функции в классе #6
Цитата Сообщение от ShadowFirst Посмотреть сообщение
Может я чего не понимаю но почему основные ваши функции находятся в privet, а для их вызова используются промежуточные функции. В чем проблема сразу их сделать public?

А если по теме то например от одной функции можно точно избавиться, которая вам выдает количество элементов в дереве, вернее не совсем избавиться а просто каждый раз не обходить это дерево для того что бы узнать количество элементов, заменив на статическую переменную, которая будет прибавляться на 1 при добавлении элемента и уменьшаться при удалении.
Об этом и тема, в private находятся рекурсивные функции, которые сами по себе не вызвать. А в private они для того, чтобы не путаться при вызове методов.

А Насчет подсчета количества элементов неплохая идея, позже так и сделаю.

Добавлено через 14 минут
Цитата Сообщение от ForEveR Посмотреть сообщение
Явный вызов деструкторов точно следует убрать. delete вызовет деструктор сам.
Точно, там была ошибка. Вместо вызова деструкторов должна вызываться функция Delete().
Yandex
Объявления
12.11.2013, 13:21     Рекурсивные функции в классе
Ответ Создать тему
Опции темы

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