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

Класс бинарное дерево - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.63
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 09:18     Класс бинарное дерево #1
Здравствуйте.
Требуется написать англо-русский словарь на основе бинарного дерева. Не полностью понимаю, как будет выглядеть класс. Каждое слово должно быть элементом бинарного дерева, в котором будет ссылка на следующее, предыдущее слово и перевод, насколько понимаю, но тогда структура выстроится с линейный список.
Помогите описать класс, сам не могу разобраться.
Заранее спасибо.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.02.2011, 09:49     Класс бинарное дерево #2
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
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 10:14  [ТС]     Класс бинарное дерево #3
Спасибо, конечно, но я просил всего лишь подсказать )) ладно, попробую разобраться
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.02.2011, 10:22     Класс бинарное дерево #4
phx, вас не поймёшь. Гайдов по бинарным деревьям (да и по всяким другим) куча в интернете, гугли не хочу. Раз вы решили обратиться за динамической помощью (форум, живое общение), то я полагаю, что статическая (статьи) вам не помогла. Я вам дал класс, вы смотрите и спрашивайте, что непонятно. А то "помогите описать класс". Чтобы получить "просто подсказку", надо задавать конкретные вопросы, например "я не понимаю, как посчитать глубину". А "помогите описать класс" - звучит как "напишите программу за меня ПЛЗ".
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 12:14  [ТС]     Класс бинарное дерево #5
Я написал, что не понимаю, какие поля должны быть в классе. По вашему коду пытаюсь это понять. А весь код программы я не просил писать.

Добавлено через 27 минут
Зачем вы используете дружественный класс (если это так называется), что он делает?
Цитата Сообщение от silent_1991 Посмотреть сообщение
friend class Tree< T >;
Разве нельзя реализовать класс как-то проще? Элемент бинарного дерева - слово. То есть, в одном поле элемента должен быть перевод, 2 других поля должны указывать на следующее и предыдущее слово. Или и здесь я не понял связи бинарного дерева со словарем?

Добавлено через 11 минут
ладно, с дружественным классом разобрался, вроде...

Добавлено через 58 минут
silent_1991, касаемо логики работы программы, исправьте, где я неправильно понял:
В программе должен быть класс, элементы этого класса - буквы, в каждой из которых по ещё одному классу (В котором все слова, начинающиеся на эту букву и указатели на предыдущее и следующее слово), указатели на предыдующую и следюущую буквы. Тут все правильно?
igorrr37
 Аватар для igorrr37
1593 / 1221 / 118
Регистрация: 21.12.2010
Сообщений: 1,868
Записей в блоге: 7
26.02.2011, 12:54     Класс бинарное дерево #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
#include<iostream>
#include<windows.h>
 
class Tree{
    private:
    class Node{
        private:
        std::string eng;
        std::string rus;
        Node* left;
        Node* right;
        public:
        Node(std::string a, std::string b):eng(a), rus(b), left(NULL), right(NULL){}
        void insert(std::string a, std::string b){
            if(a>eng&&right) right->insert(a, b);
            else if(a>eng&&!right) right=new Node(a, b);
            else if(a<eng&&left) left->insert(a, b);
            else left=new Node(a, b);
        }
        void print(){
            if(left) left->print();
            std::cout<<eng<<" - "<<rus<<"\n";
            if(right) right->print();
        }
    };
    Node* root;
    public:
    Tree():root(NULL){}
    void insert(std::string, std::string);
    void print();
};
 
void Tree::insert(std::string a, std::string b){
    if(!root) root=new Node(a, b);
    else root->insert(a, b);
}
 
void Tree::print(){
    root->print();
}
 
int main(){
    SetConsoleOutputCP(1251);
    SetConsoleCP(1251);
    Tree dict;
    dict.insert("zero", "нуль");
    dict.insert("achieve", "достигать");
    dict.insert("main", "главный");
    dict.insert("apply", "применять");
    dict.print();
}
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 13:24  [ТС]     Класс бинарное дерево #7
igorrr37, спасибо, стало намного понятнее. Вы используете std::string, но можно подключить модуль string, и использовать тип не std::string, а string. Есть принципиальная разница?
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
26.02.2011, 13:29     Класс бинарное дерево #8
phx, std::string http://www.cyberforum.ru/cgi-bin/latex.cgi?\Leftrightarrow string, просто в первом случае мы явно указываем пространство имен.
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 13:44  [ТС]     Класс бинарное дерево #9
asics, ясно, спасибо, буду знать.
И ещё глупый вопрос:
В классе в private мы указываем переменные, к которым могут обращаться только объекты класса, в public указываем переменные, доступные из любого места программы, а так же методы.
А эта строка
Цитата Сообщение от igorrr37 Посмотреть сообщение
Node(std::string a, std::string b):eng(a), rus(b), left(NULL), right(NULL){}
нужна для того, чтобы внешним подпрограммам обращаться к переменным из private, я правильно понял?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
26.02.2011, 13:48     Класс бинарное дерево #10
phx, Это конструктор. Так как сам класс Node описан в закрытом разделе класса Tree, то извне не обратиться, только из самого класса Tree или Node.
bigredcat
364 / 311 / 3
Регистрация: 24.02.2011
Сообщений: 1,512
Записей в блоге: 1
26.02.2011, 13:55     Класс бинарное дерево #11
Цитата Сообщение от phx Посмотреть сообщение
asics, ясно, спасибо, буду знать.
И ещё глупый вопрос:
А эта строка

нужна для того, чтобы внешним подпрограммам обращаться к переменным из private, я правильно понял?
Это конструктор класса, а после двоеточия идет инициализация полей класса указанными значениями
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 13:57  [ТС]     Класс бинарное дерево #12
ForEveR, спасибо большое, теперь, пожалуй, все ясно.
igorrr37, вам особая благодарность!
silent_1991, в вашем коде, к сожалению, окончательно разобраться так и не смог...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.02.2011, 14:09     Класс бинарное дерево
Еще ссылки по теме:

Бинарное дерево C++
C++ Нужно реализовать класс Бинарное дерево.
C++ Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.02.2011, 14:09     Класс бинарное дерево #13
phx, по поводу моей программы - это универсальный класс дерева, элементами его могут быть любые данные (в том числе экземпляры структур и классов). Вам осталось бы просто написать собственный тип данных, который был бы узлом дерева. Обобщённое программирование решает.
Yandex
Объявления
26.02.2011, 14:09     Класс бинарное дерево
Ответ Создать тему
Опции темы

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