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

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

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

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

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

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

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

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

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

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

Бинарное дерево - C++
дано целочисленнное бинарное дерево. найти: а)количество вершин дереваж б)значение самой левой вершины в правом поддереве в)...

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

Бинарное дерево - C++
Друзья, помогите реализовать задачу в виде бинарного дерева: Оператор мобильной связи организовал базу данных абонентов,...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт С++
4960 / 3036 / 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
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 10:14  [ТС]     Класс бинарное дерево #3
Спасибо, конечно, но я просил всего лишь подсказать )) ладно, попробую разобраться
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
1643 / 1271 / 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();
}
phx
0 / 0 / 0
Регистрация: 21.02.2011
Сообщений: 17
26.02.2011, 13:24  [ТС]     Класс бинарное дерево #7
igorrr37, спасибо, стало намного понятнее. Вы используете std::string, но можно подключить модуль string, и использовать тип не std::string, а string. Есть принципиальная разница?
asics
Freelance
Эксперт С++
2846 / 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, просто в первом случае мы явно указываем пространство имен.
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
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
26.02.2011, 13:48     Класс бинарное дерево #10
phx, Это конструктор. Так как сам класс Node описан в закрытом разделе класса Tree, то извне не обратиться, только из самого класса Tree или Node.
bigredcat
365 / 312 / 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++
Подскажите как дополнить код,что бы получился полноценный прямой обход бинарного дерева... #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

Бинарное дерево - C++
Не получается написать функцию для вывода дерева на экран. Работает она как-то не правильно. Помогите, пожалуйста, срочно. ВОт часть кода: ...

Бинарное дерево - C++
Здравствуйте, нужно помощь в написании программы. Условие: Каждая вершина бинарного дерева содержит: - 2 указателя (на каждый...

Бинарное дерево - C++
Привет Делаю бинарное дерево, пытаюсь добавить элемент. Что делаю не так? Класс дерева struct node{ int data; //поле...

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


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

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

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