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

бинарные деревья - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
graf1
2 / 0 / 1
Регистрация: 22.03.2010
Сообщений: 18
03.02.2011, 21:32     бинарные деревья #1
Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддеревья. Строки в дереве упорядочены по возрастанию. Написать функции включения строки и получения указателя на строку по заданному номеру, который строки имеет в упорядоченной последовательности.

заранее спасибо
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.02.2011, 21:32     бинарные деревья
Посмотрите здесь:

Бинарные деревья C++
Бинарные деревья C++
Бинарные деревья C++
Бинарные деревья C++
C++ Бинарные деревья
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
03.02.2011, 21:44     бинарные деревья #2
Ииии? Что непонятно?
graf1
2 / 0 / 1
Регистрация: 22.03.2010
Сообщений: 18
03.02.2011, 21:53  [ТС]     бинарные деревья #3
проблема в том, что я не знаю как выполнять задания с помощью бинарных деревьев, да и вообще с программированием неочень( я люблю it а там без этого никак)
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
03.02.2011, 22:03     бинарные деревья #4

Не по теме:

Похоже на "я очень люблю есть, но совсем не умею готовить". Не хочу никого переубеждать и поучать, но если не получается, может лучше не браться? А то и обжечься можно...



Так, это было не по теме. Теперь по теме: если я чего-то не знаю, я беру соответствующую литературу и начинаю производить один из основополагающих процессов, который мы все производим каждый день: процесс познания. Не ждите, что кто-то придёт и напишет за вас одну лабу, потому другую, потом экзамен, а потом и диплом за вас получит. Гуглите по теме бинарных деревьев и изучайте их. Читайте книги по Си++. Благо, и того, и другого в интернете навалом, хорошего и разного. Бинарные деревья несложные, язык посложнее. Но вас никто не тянул за руку в вашу любимую IT, и раз уж вы сюда пришли - изучайте, пробуйте, ошибайтесь и снова пробуйте.
graf1
2 / 0 / 1
Регистрация: 22.03.2010
Сообщений: 18
03.02.2011, 22:11  [ТС]     бинарные деревья #5
Совет конечно хороший, я так делаю. Но сейчас мне нужен просто код, я в нем разбираюсь и потихоньку понимаю его.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
03.02.2011, 22:29     бинарные деревья #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Писать код полностью не буду, писал когда-то для себя просто шаблонный клас двоичного дерева. Вот его и выложу.

TreeNode.h
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
#ifndef TREENODE_H
#define TREENODE_H
 
template< typename T > class Tree;
 
template< typename T >
class TreeNode
{
    friend class Tree< T >;
 
public:
    TreeNode();
    TreeNode(const T &);
 
    T get_data() const;
 
private:
    T _data;
    TreeNode< T > *_left;
    TreeNode< T > *_right;
};
 
template< typename T >
TreeNode< T >::TreeNode():
_left(0),
_right(0)
{
}
 
template< typename T >
TreeNode< T >::TreeNode(const T &data):
_data(data),
_left(0),
_right(0)
{
}
 
template< typename T >
T TreeNode< T >::get_data() const
{
    return _data;
}
 
#endif
Tree.h
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
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
#ifndef TREE_H
#define TREE_H
 
#include "TreeNode.h"
 
template< typename T >
class Tree
{
    template< typename Type >
    friend Type max(const Type &, const Type &);
 
public:
    Tree();
    ~Tree();
 
    void insert(const T &);
    void remove(const T &);
 
    void pre_order() const;
    void in_order() const;
    void post_order() const;
 
    int depth() const;
 
    void print() const;
 
private:
    TreeNode< T > *_root;
 
    void insert_helper(TreeNode< T > **, const T &);
    void remove_helper(TreeNode< T > **, const T &);
 
    void pre_order_helper(TreeNode< T > *) const;
    void in_order_helper(TreeNode< T > *) const;
    void post_order_helper(TreeNode< T > *) const;
 
    void delete_helper(TreeNode< T > *);
 
    int depth_helper(TreeNode< T > *) const;
 
    void print_helper(TreeNode< T >*, int) const;
};
 
template< typename T >
Tree< T >::Tree():
_root(0)
{
}
 
template< typename T >
Tree< T >::~Tree()
{
    delete_helper(_root);
}
 
template< typename T >
void Tree< T >::delete_helper(TreeNode< T > *node)
{
    if (node != 0)
    {
        delete_helper(node->_left);
        delete_helper(node->_right);
 
        delete node;
    }
}
 
template< typename T >
void Tree< T >::insert(const T &data)
{
    insert_helper(&_root, data);
}
 
template< typename T >
void Tree< T >::insert_helper(TreeNode< T > **node, const T &data)
{
    if (*node == 0)
        *node = new TreeNode< T > (data);
    else
    {
        if ((*node)->_data > data)
            insert_helper(&((*node)->_left), data);
        else
        {
            if ((*node)->_data < data)
                insert_helper(&((*node)->_right), data);
        }
    }
}
 
template< typename T >
void Tree< T >::remove(const T &data)
{
    remove_helper(&_root, data);
}
 
template< typename T >
void Tree< T >::remove_helper(TreeNode< T > **node, const T &data)
{
    if ((*node)->_data == data)
    {
        TreeNode< T > *del_node = *node;
 
        if ((*node)->_left == 0 && (*node)->_right == 0)
        {
            *node = 0;
 
            delete del_node;
        }
        else
        {
            if ((*node)->_left == 0)
            {
                *node = (*node)->_right;
 
                delete del_node;
            }
            else
            {
                if ((*node)->_right == 0)
                {
                    *node = (*node)->_left;
 
                    delete del_node;
                }
                else
                {
                    TreeNode< T > *p = *node;
                    TreeNode< T > *i = (*node)->_left;
 
                    while (i->_right != 0)
                    {
                        p = i;
                        i = i->_right;
                    }
 
                    *node = i;
                    p->_right = i->_left;
                    i->_right = del_node->_right;
                    i->_left = p;
 
                    delete del_node;
                }
            }
        }
    }
    else
    {
        if ((*node)->_data > data)
            remove_helper(&((*node)->_left), data);
        else
        {
            if ((*node)->_data < data)
                remove_helper(&((*node)->_right), data);
        }
    }
}
 
template< typename T >
void Tree< T >::pre_order() const
{
    pre_order_helper(_root);
}
 
template< typename T >
void Tree< T >::pre_order_helper(TreeNode< T > *node) const
{
    if (node != 0)
    {
        std::cout << node->_data << "  ";
 
        pre_order_helper(node->_left);
        pre_order_helper(node->_right);
    }
}
 
template< typename T >
void Tree< T >::in_order() const
{
    in_order_helper(_root);
}
 
template< typename T >
void Tree< T >::in_order_helper(TreeNode< T > *node) const
{
    if (node != 0)
    {
        in_order_helper(node->_left);
 
        std::cout << node->_data << "  ";
 
        in_order_helper(node->_right);
    }
}
 
template< typename T >
void Tree< T >::post_order() const
{
    post_order_helper(_root);
}
 
template< typename T >
void Tree< T >::post_order_helper(TreeNode< T > *node) const
{
    if (node != 0)
    {
        post_order_helper(node->_left);
        post_order_helper(node->_right);
 
        std::cout << node->_data << "  ";
    }
}
 
template< typename T >
int Tree< T >::depth() const
{
    return depth_helper(_root);
}
 
template< typename T >
int Tree< T >::depth_helper(TreeNode< T > *node) const
{
    if (node->_left == 0 && node->_right == 0)
        return 1;
    else
    {
        if (node->_left == 0)
            return 1 + depth_helper(node->_right);
        else
        {
            if (node->_right == 0)
                return 1 + depth_helper(node->_left);
            else
                return 1 + max(depth_helper(node->_left), depth_helper(node->_right));
        }
    }
}
 
template< typename T >
void Tree< T >::print() const
{
    print_helper(_root, 0);
}
 
template< typename T >
void Tree< T >::print_helper(TreeNode< T > *node, int spaces) const
{
    while (node != 0)
    {
        print_helper(node->_right, spaces + 5);
 
        for (int i = 1; i < spaces; ++i)
            std::cout << ' ';
 
        std::cout << node->_data << std::endl;
 
        node = node->_left;
        spaces += 5;
    }
}
 
template< typename Type >
Type max(const Type &left, const Type &right)
{
    return left > right ? left : right;
}
 
#endif
graf1
2 / 0 / 1
Регистрация: 22.03.2010
Сообщений: 18
03.02.2011, 22:56  [ТС]     бинарные деревья #7
спасибо
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 01:12     бинарные деревья #8
silent_1991, прости за столь интимный вопрос: а почему дерево является другом своего узла? В смысле, зачем определять узел дерева отдельно от самого дерева, порождая тем самым лишние проблемы и лишние шаблоны.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
04.02.2011, 11:45     бинарные деревья #9
volovzi, и в чём же лишние проблемы? У нас есть основная часть - узел, который содержит указатели на поддеревья и данные, которые должны в дереве храниться. И есть собственно дерево - обёртка, в ней основные функции работы с деревом и только указатель на корень дерева. Весь цивилизованный мир так делает, для большинства структур данных этот способ подходит, и является, кстати, очень удобным. Например, для связного списка точно так же, делаем узел списка, который содержит указатель на следующий элемент (и, в случае двусвязного списка, на предыдущий) и данные, и делаем обёртку - основные функции работы со списком и указатели на начало и конец. Дружбу устанавливаем для свободного доступа к данным и указателям, без сеттеров/геттеров.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 12:05     бинарные деревья #10
silent_1991, я не о том спрашиваю. Зачем делать узел дерева отдельно от дерева, если он больше нигде не используется?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
04.02.2011, 12:16     бинарные деревья #11
volovzi, я же сказал, у нас есть основная часть - узел (в нём хранятся данные и указатели на поддеревья) и обёртка - указатель на корень и функции обработки. По мне, так конфету с фантиком не надо соединять, пусть будут отдельно, так ведь удобнее.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 12:20     бинарные деревья #12
silent_1991, ты не понял. Я вот что имею в виду:
Написать класс, описывающий дерево
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
04.02.2011, 12:30     бинарные деревья #13
Ладно, так: зачем в обёртку, функциям которой нужно знать только одно - откуда начинается дерево, делать одновременно и узлом?
Давайте представим что мы не знает ООП вообще, и Си++ в частности. Как бы мы писали всё это дело, скажем, на Си? Вы бы написали структуру, представляющую узел, которая хранит данные и указатели. Во "внешней среде" мы бы хранили указатель на корень (возможно, это была бы глобальная переменная) и описали бы функции работы с деревом. А теперь мы вдруг знаем ООП и Си++. Так давайте эту "внешнюю среду" сожмём до уровня, на котором она действительно нужна - до уровня обёртки, которая содержит указатель на корень и функции обработки. И общаться с собственно деревом будем посредством этой обёртки, а не посредством "внешней среды" в стиле Си.

Добавлено через 1 минуту
Отвечаю: мне так захотелось. Вдруг я захочу сделать узел универсальным, для любых деревьев. Тогда мне придётся изменить сам TreeNode, но зато доступ к нему будут иметь и класс универсальных деревьев, и бинарных, и красно-чёрных и т.д.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 12:34     бинарные деревья #14
silent_1991, тогда нужно в дерево передавать в качестве параметра шаблона не тип данных, а тип узла и делать универсальным не узел, а дерево .
Узел красно-чёрного будет отличаться от узла другого дереве, так что в разных деревьях их использовать не получится.

Вот, собственно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename Node>
class tree {    
public:
    typedef Node node_type;
    typedef typename node_type::value_type value_type;
 
    tree () : root(0) {}
    ~tree () { delete root; }
    
    void insert (const value_type & value) {
        if (root == 0) root = new node_type(value);
        else root->insert(value);
    }
    
private:
    node_type * root;
};
Вставляешь любой узел и получаешь универсальное дерево. А основные операции (поворот, балансировка) в любом случае производятся в узлах.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
04.02.2011, 12:38     бинарные деревья #15
volovzi, я, честно говря, так и не понял, о чём идёт спор Вы сделали в своём классе так, я иначе. От моего решения класс дерева пострадает по отношению к вашему? Нет. Так к чему придираться?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 12:46     бинарные деревья #16
silent_1991, это не спор, это попытка найти оптимальное решение. Мне интересно, вот и копаю.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
04.02.2011, 12:47     бинарные деревья #17
volovzi, я всегда со всеми структурами данных так делал, отдельно описывал узел, отдельно обёртку. И у многих авторов обучающей литературы этот подход встречал.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.02.2011, 12:50     бинарные деревья #18
В случае дерева вообще не нужен тип всего контейнера, всё делает класс узла. Да и к любым другим спискам это тоже относится. Разделить же на два типа можно только тип поля данных и класс узла. Кстати, это разделение как раз и целесообразно и не только для списков.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 12:55     бинарные деревья #19
taras atavin, контейнер не обязателен, но весьма полезен. Он хранит первый элемент, а так же дополнительные данные (последний элемент, размер и т.п.).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.02.2011, 12:58     бинарные деревья
Еще ссылки по теме:

бинарные деревья С++ C++
C++ Бинарные деревья
Бинарные деревья C++

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.02.2011, 12:58     бинарные деревья #20
Ну если только для дополнительных данных, но последний элемент имеет хоть какой то смысл только у линейных списков. Во что тогда превращается тип дерева? В оболочку только лишь для указателя на корень, чей тип и так описан.
Yandex
Объявления
04.02.2011, 12:58     бинарные деревья
Ответ Создать тему
Опции темы

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