Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 51, средняя оценка - 4.63
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
#1

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

26.02.2011, 09:18. Просмотров 8447. Ответов 12
Метки нет (Все метки)

Здравствуйте.
Требуется написать англо-русский словарь на основе бинарного дерева. Не полностью понимаю, как будет выглядеть класс. Каждое слово должно быть элементом бинарного дерева, в котором будет ссылка на следующее, предыдущее слово и перевод, насколько понимаю, но тогда структура выстроится с линейный список.
Помогите описать класс, сам не могу разобраться.
Заранее спасибо.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2011, 09:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Класс бинарное дерево (C++):

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

Описать класс, реализующий бинарное дерево - C++
Здравствуйте! Возникли проблемы с реализацией одной программы ....Описать класс, реализующий бинарное дерево, обладающее возможностью...

Нужно реализовать класс Бинарное дерево. - C++
Нужно реализовать класс Бинарное дерево. Вот класс template <class T> class Tree { private: class Item{ friend Tree; ...

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

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Бинарное дерево - C++
Народ помогите. На С++ нада написать программу бинарного дерева Требования: 1. В программе должен быть шаблонный класс (template...

12
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
1
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 10:14  [ТС] #3
Спасибо, конечно, но я просил всего лишь подсказать )) ладно, попробую разобраться
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
26.02.2011, 10:22 #4
phx, вас не поймёшь. Гайдов по бинарным деревьям (да и по всяким другим) куча в интернете, гугли не хочу. Раз вы решили обратиться за динамической помощью (форум, живое общение), то я полагаю, что статическая (статьи) вам не помогла. Я вам дал класс, вы смотрите и спрашивайте, что непонятно. А то "помогите описать класс". Чтобы получить "просто подсказку", надо задавать конкретные вопросы, например "я не понимаю, как посчитать глубину". А "помогите описать класс" - звучит как "напишите программу за меня ПЛЗ".
1
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, касаемо логики работы программы, исправьте, где я неправильно понял:
В программе должен быть класс, элементы этого класса - буквы, в каждой из которых по ещё одному классу (В котором все слова, начинающиеся на эту букву и указатели на предыдущее и следующее слово), указатели на предыдующую и следюущую буквы. Тут все правильно?
0
igorrr37
1648 / 1276 / 133
Регистрация: 21.12.2010
Сообщений: 1,932
Записей в блоге: 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();
}
3
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 13:24  [ТС] #7
igorrr37, спасибо, стало намного понятнее. Вы используете std::string, но можно подключить модуль string, и использовать тип не std::string, а string. Есть принципиальная разница?
0
asics
Freelance
Эксперт С++
2848 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
26.02.2011, 13:29 #8
phx, std::string http://www.cyberforum.ru/cgi-bin/latex.cgi?\Leftrightarrow string, просто в первом случае мы явно указываем пространство имен.
2
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, я правильно понял?
0
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,545
Завершенные тесты: 3
26.02.2011, 13:48 #10
phx, Это конструктор. Так как сам класс Node описан в закрытом разделе класса Tree, то извне не обратиться, только из самого класса Tree или Node.
2
bigredcat
366 / 313 / 3
Регистрация: 24.02.2011
Сообщений: 1,512
Записей в блоге: 1
26.02.2011, 13:55 #11
Цитата Сообщение от phx Посмотреть сообщение
asics, ясно, спасибо, буду знать.
И ещё глупый вопрос:
А эта строка

нужна для того, чтобы внешним подпрограммам обращаться к переменным из private, я правильно понял?
Это конструктор класса, а после двоеточия идет инициализация полей класса указанными значениями
0
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 13:57  [ТС] #12
ForEveR, спасибо большое, теперь, пожалуй, все ясно.
igorrr37, вам особая благодарность!
silent_1991, в вашем коде, к сожалению, окончательно разобраться так и не смог...
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
26.02.2011, 14:09 #13
phx, по поводу моей программы - это универсальный класс дерева, элементами его могут быть любые данные (в том числе экземпляры структур и классов). Вам осталось бы просто написать собственный тип данных, который был бы узлом дерева. Обобщённое программирование решает.
2
26.02.2011, 14:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.02.2011, 14:09
Привет! Вот еще темы с ответами:

Бинарное дерево - C++
Помогите пожалуйста с программой. Нужно сделать обход, слева и справа(функции get_left и get_right), желательно обход в глубину. И...

Бинарное дерево - C++
Объясните пжлст почему не работает программа...при вводе файла пишет -842150451 /*Дан адрес P1 вершины дерева — записи типа TNode, ...

Бинарное дерево - C++
Подскажите как дополнить код,что бы получился полноценный прямой обход бинарного дерева... #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

Бинарное дерево - C++
Здравствуйте.Прошу помощи.Никак не могу разобраться в задании.Нужно сделать бинарное дерево и с помощью дерева привести выражение к...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

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