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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.68
graf1
2 / 0 / 1
Регистрация: 22.03.2010
Сообщений: 18
#1

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

03.02.2011, 21:32. Просмотров 2580. Ответов 28
Метки нет (Все метки)

Вершина двоичного дерева содержит указатель на строку и указатели на правое и левое поддеревья. Строки в дереве упорядочены по возрастанию. Написать функции включения строки и получения указателя на строку по заданному номеру, который строки имеет в упорядоченной последовательности.

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

Бинарные деревья - C++
Очень нужна помощь, вообще деревья не понимаю!!!:( Вершина дерева содержит указатель на строку и N указателей на потомков. Функция...

Бинарные деревья - C++
Здравствуйте! Подскажите, правильно ли написано правое удаление вершины дерева? if(tree1->Right){ if(tree1->Right->Left==NULL){ ...

Бинарные деревья - C++
Компилятор выдаёт ошибки в 9, 10 и 12, 13 строках: invalid conversion from 'int' to 'sNode*' Подскажите пожалуйста, что не так. ...

Бинарные деревья - C++
Доброго времени суток, нужна помощь, дали задание...Вершина бинарного дерева содержит ключ, строку и два указателя на потомков.Составить...

Бинарные деревья - C++
1)Написать программу подсчета числа вершин в бинарном дереве 2)Написать программу копирования одного бинарного дерева в другое ...

Бинарные деревья - C++
Имею три файла: Скажите пожалуйста почему я не могу создать э-т m?(Класс tree) Он мне пишет - undefined reference to...

Бинарные деревья - C++
На с++ с объектно-ориентированным подходом(тоисть с помощю класов) нужно представить арифметическое выражение типа 3*((7+1)/4)+(17-5) в...

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

Не по теме:

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



Так, это было не по теме. Теперь по теме: если я чего-то не знаю, я беру соответствующую литературу и начинаю производить один из основополагающих процессов, который мы все производим каждый день: процесс познания. Не ждите, что кто-то придёт и напишет за вас одну лабу, потому другую, потом экзамен, а потом и диплом за вас получит. Гуглите по теме бинарных деревьев и изучайте их. Читайте книги по Си++. Благо, и того, и другого в интернете навалом, хорошего и разного. Бинарные деревья несложные, язык посложнее. Но вас никто не тянул за руку в вашу любимую IT, и раз уж вы сюда пришли - изучайте, пробуйте, ошибайтесь и снова пробуйте.
graf1
2 / 0 / 1
Регистрация: 22.03.2010
Сообщений: 18
03.02.2011, 22:11  [ТС]     бинарные деревья #5
Совет конечно хороший, я так делаю. Но сейчас мне нужен просто код, я в нем разбираюсь и потихоньку понимаю его.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 01:12     бинарные деревья #8
silent_1991, прости за столь интимный вопрос: а почему дерево является другом своего узла? В смысле, зачем определять узел дерева отдельно от самого дерева, порождая тем самым лишние проблемы и лишние шаблоны.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
04.02.2011, 11:45     бинарные деревья #9
volovzi, и в чём же лишние проблемы? У нас есть основная часть - узел, который содержит указатели на поддеревья и данные, которые должны в дереве храниться. И есть собственно дерево - обёртка, в ней основные функции работы с деревом и только указатель на корень дерева. Весь цивилизованный мир так делает, для большинства структур данных этот способ подходит, и является, кстати, очень удобным. Например, для связного списка точно так же, делаем узел списка, который содержит указатель на следующий элемент (и, в случае двусвязного списка, на предыдущий) и данные, и делаем обёртку - основные функции работы со списком и указатели на начало и конец. Дружбу устанавливаем для свободного доступа к данным и указателям, без сеттеров/геттеров.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 12:05     бинарные деревья #10
silent_1991, я не о том спрашиваю. Зачем делать узел дерева отдельно от дерева, если он больше нигде не используется?
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
04.02.2011, 12:16     бинарные деревья #11
volovzi, я же сказал, у нас есть основная часть - узел (в нём хранятся данные и указатели на поддеревья) и обёртка - указатель на корень и функции обработки. По мне, так конфету с фантиком не надо соединять, пусть будут отдельно, так ведь удобнее.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
04.02.2011, 12:20     бинарные деревья #12
silent_1991, ты не понял. Я вот что имею в виду:
Написать класс, описывающий дерево
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
04.02.2011, 12:30     бинарные деревья #13
Ладно, так: зачем в обёртку, функциям которой нужно знать только одно - откуда начинается дерево, делать одновременно и узлом?
Давайте представим что мы не знает ООП вообще, и Си++ в частности. Как бы мы писали всё это дело, скажем, на Си? Вы бы написали структуру, представляющую узел, которая хранит данные и указатели. Во "внешней среде" мы бы хранили указатель на корень (возможно, это была бы глобальная переменная) и описали бы функции работы с деревом. А теперь мы вдруг знаем ООП и Си++. Так давайте эту "внешнюю среду" сожмём до уровня, на котором она действительно нужна - до уровня обёртки, которая содержит указатель на корень и функции обработки. И общаться с собственно деревом будем посредством этой обёртки, а не посредством "внешней среды" в стиле Си.

Добавлено через 1 минуту
Отвечаю: мне так захотелось. Вдруг я захочу сделать узел универсальным, для любых деревьев. Тогда мне придётся изменить сам TreeNode, но зато доступ к нему будут иметь и класс универсальных деревьев, и бинарных, и красно-чёрных и т.д.
volovzi
267 / 169 / 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;
};
Вставляешь любой узел и получаешь универсальное дерево. А основные операции (поворот, балансировка) в любом случае производятся в узлах.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.02.2011, 12:38     бинарные деревья
Еще ссылки по теме:

Бинарные деревья - C++
Разработать набор классов упорядоченных бинарных деревьев поиска типов: вещественные числа, двоичные строки(строка из 0 и 1) и линейные...

Бинарные деревья - C++
Вот задачка: Для заданного бинарного дерева поиска проверить условие: • для каждой вершины высота левого поддерева отличается от...

бинарные деревья - C++
Здравствуйте! Помогите пожалуйста доделать задачу на бинарные деревья. Язык только начали изучать. Дается не очень легко. Пока...

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

Бинарные деревья С++ - C++
Добрый день! Дали такое задание на лабораторную работу. кое-что получилось, а в остальном прошу Вас помочь... Из входной...


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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
04.02.2011, 12:38     бинарные деревья #15
volovzi, я, честно говря, так и не понял, о чём идёт спор Вы сделали в своём классе так, я иначе. От моего решения класс дерева пострадает по отношению к вашему? Нет. Так к чему придираться?
Yandex
Объявления
04.02.2011, 12:38     бинарные деревья
Ответ Создать тему
Опции темы

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