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

Как вы учили деревья - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
Джек
5 / 5 / 0
Регистрация: 16.08.2011
Сообщений: 77
25.11.2012, 00:39     Как вы учили деревья #1
Здравствуйте. Помогите освоить деревя на с++. Ну например как кто учил может есть какая нить литература по ним или код где хорошо все описано, или алгоритм как построить древо. В гугле полно информации но не все понятно. Я думаю многие сталкивались с такой проблемой да может есть ссылки на полезную инфу. Заранее спасибо.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.11.2012, 00:39     Как вы учили деревья
Посмотрите здесь:

C++ C++ деревья
Б деревья C++
C++ Как Вы учили С++
C++ деревья
Деревья на с++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.11.2012, 00:48     Как вы учили деревья #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Джек, листик и ручка.
mmd
13 / 13 / 1
Регистрация: 17.05.2012
Сообщений: 80
25.11.2012, 00:51     Как вы учили деревья #3
Кормена почитай там про деревья есть
теорию графов, но это более формально
Джек
5 / 5 / 0
Регистрация: 16.08.2011
Сообщений: 77
25.11.2012, 01:22  [ТС]     Как вы учили деревья #4
Цитата Сообщение от go Посмотреть сообщение
Джек, листик и ручка.
Ну а серьйозно что то есть?
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,919
Записей в блоге: 2
Завершенные тесты: 1
25.11.2012, 01:26     Как вы учили деревья #5
Цитата Сообщение от Джек Посмотреть сообщение
Ну а серьйозно что то есть?
а серьезно, так и надо.
Джек
5 / 5 / 0
Регистрация: 16.08.2011
Сообщений: 77
29.11.2012, 01:33  [ТС]     Как вы учили деревья #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
class Tree
{private:
struct Node
{Node *left;
Node *right;
int data;
Node(){left=right=0;data=0;}
};
Node *root;
public:
Tree(){root=0;}
void add(int x)
{Node *r=new Node;
if(root==NULL)
r->data=x;
root=r;
 
if(x>r->data)
r->data=x;
r->right=r;
if(x<r->data)
r->data=x;
r->left=r;
cout<<r->right->data<<endl;
cout<<r->left->data<<endl;
 
}
 
};
int main()
{Tree f;
f.add(1);
f.add(5);
f.add(6);
getch();
        return 0;
}
//---------------------------------------------------------------------------
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
29.11.2012, 01:35     Как вы учили деревья #7

Не по теме:

Джек, теги-теги-теги...



Добавлено через 2 минуты
код с тегами:
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
class Tree
 {private:
 struct Node
 {Node *left;
 Node *right;
 int data;
 Node(){left=right=0;data=0;}
 };
 Node *root;
 public:
 Tree(){root=0;}
 void add(int x)
 {Node *r=new Node;
 if(root==NULL)
 r->data=x;
 root=r;
 
 if(x>r->data)
 r->data=x;
 r->right=r;
 if(x<r->data)
 r->data=x;
 r->left=r;
 cout<<r->right->data<<endl;
 cout<<r->left->data<<endl;
 
 }
 
 };
 int main()
 {Tree f;
 f.add(1);
 f.add(5);
 f.add(6);
 getch();
 return 0;
 }
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
29.11.2012, 03:50     Как вы учили деревья #8
фигурных скобок в if-ах не хватает.
приоритет операторов в выражениях cout<< может преподнести сюрприз - ставь скобки
это синтаксические ошибки.

А по сути: прохода в глубину дерева нет вообще: элемент добавляется или в корень->справа или в корень->слева или в сам корень.
четвёртого видимо не дано.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
29.11.2012, 06:54     Как вы учили деревья #9
Цитата Сообщение от Джек Посмотреть сообщение
struct Node
Это тоже лучше классом с publc членами. И деструктора не хватает, который при удалении узла сотрёт всё его поддерво.

Добавлено через 2 минуты
Цитата Сообщение от Джек Посмотреть сообщение
{Node *r=new Node;
Показалось, что root=new Node;, это была бы утечка, так как корень может быть уже создан, да и не дерево, так как исключается создание потомков корня.

Добавлено через 1 минуту
Цитата Сообщение от I.M. Посмотреть сообщение
root=r;
с учётом предыдущих строк, это эквивалент root=new Node;.

Добавлено через 2 минуты
Надо в скобку, так как условие должно относиться к обоим действиям:
C++
1
2
3
4
5
if(root==NULL)
{
 r->data=x;
 root=r;
}
Добавлено через 2 минуты
Цитата Сообщение от Джек Посмотреть сообщение
if(x>r->data)
r->data=x;
r->right=r;
right всегда будет копией корня, смысл потомка в хранении собственной инфы, то есть это не потомок. Надо так:
C++
1
2
3
4
5
if(x>r->data)
{
 r->data=x;
 r->right=r;
}
.

Добавлено через 27 секунд
Цитата Сообщение от I.M. Посмотреть сообщение
if(x<r->data)
*r->data=x;
*r->left=r;
То же самое.
Джек
5 / 5 / 0
Регистрация: 16.08.2011
Сообщений: 77
29.11.2012, 09:12  [ТС]     Как вы учили деревья #10
А как проверить какое слева значение и с права. Покажите пожалуйста.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
29.11.2012, 09:15     Как вы учили деревья #11
TArray.hpp:
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
#ifndef TARRAY_HPP_INCLUDED
#define TARRAY_HPP_INCLUDED
//=================================================================================================
template <class TItem> class TArray
{
//-------------------------------------------------------------------------------------------------
 protected:
//-------------------------------------------------------------------------------------------------
  TItem             *Data;
  size_t             Count;
//-------------------------------------------------------------------------------------------------
 public   :
//-------------------------------------------------------------------------------------------------
                     TArray          (                          );
                     TArray          (TArray           &Original);
//-------------------------------------------------------------------------------------------------
                    ~TArray          (                          );
//-------------------------------------------------------------------------------------------------
  TArray             operator =      (TArray           &Original);
//-------------------------------------------------------------------------------------------------
  TItem             &operator []     (size_t            Index   );
//-------------------------------------------------------------------------------------------------
                     operator bool   (                          );
                     operator size_t (                          );
//-------------------------------------------------------------------------------------------------
};
//=================================================================================================
template
<class TItem>
TArray <TItem> ::    TArray          (                          )
{
 Data =NULL;
 Count=0;
}
//-------------------------------------------------------------------------------------------------
template
<class TItem>
TArray <TItem> ::    TArray          (TArray           &Original)
{
 TItem *Source;
 TItem *Target;
 if (Original.Count>0)
 {
  Data=new TItem [Original.Count];
  if (Data)
  {
   for (Source=Original.Data+Original.Count-1, Target=Data+Original.Count-1; Target>=Data; --Source, --Target)
   {
    *Target=*Source;
   }
   Count=Original.Count;
  }
  else
  {
   Count=0;
  }
 }
 else
 {
  Data =NULL;
  Count=0;
 }
}
//-------------------------------------------------------------------------------------------------
template
<class TItem>
TArray <TItem> ::   ~TArray          (                          )
{
 if (Data)
 {
  delete [] Data;
 }
 Data =NULL;
 Count=0;
}
//-------------------------------------------------------------------------------------------------
template
<class TItem>
TArray <TItem>
TArray <TItem> ::    operator =      (TArray           &Original)
{
 TItem *Source;
 TItem *Target;
 if (Original.Count>0)
 {
  Data=new TItem [Original.Count];
  if (Data)
  {
   for (Source=Original.Data+Original.Count-1, Target=Data+Original.Count-1; Target>=Data; --Source, --Target)
   {
    *Target=*Source;
   }
   Count=Original.Count;
  }
  else
  {
   Count=0;
  }
 }
 else
 {
  Data =NULL;
  Count=0;
 }
 return *this;
}
//-------------------------------------------------------------------------------------------------
template
<class TItem>
TItem               &
TArray <TItem> ::    operator []     (size_t            Index   )
{
 return Data[Index];
}
//-------------------------------------------------------------------------------------------------
template
<class TItem>
TArray <TItem> ::    operator bool   (                          )
{
 return (Count>0);
}
//-------------------------------------------------------------------------------------------------
template
<class TItem>
TArray <TItem> ::    operator size_t (                          )
{
 return Count;
}
//=================================================================================================
#endif // TARRAY_HPP_INCLUDED
, TVector.hpp:
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
#ifndef TVECTOR_HPP_INCLUDED
#define TVECTOR_HPP_INCLUDED
//=================================================================================================
#include <math.h>
//=================================================================================================
class TVector
{
//-------------------------------------------------------------------------------------------------
 public   :
//-------------------------------------------------------------------------------------------------
  double             x;
  double             y;
  double             z;
//-------------------------------------------------------------------------------------------------
                     TVector         (                          );
                     TVector         (TVector          &Original);
//-------------------------------------------------------------------------------------------------
                    ~TVector         (                          );
//-------------------------------------------------------------------------------------------------
  TVector            operator =      (TVector          &Original);
//-------------------------------------------------------------------------------------------------
  TVector            operator +      (TVector          &Right   );
  void               operator +=     (TVector          &Right   );
//-------------------------------------------------------------------------------------------------
  TVector            operator -      (TVector          &Right   );
  void               operator -=     (TVector          &Right   );
//-------------------------------------------------------------------------------------------------
  TVector            operator *      (double           &Right   );
  void               operator *=     (double           &Right   );
//-------------------------------------------------------------------------------------------------
  friend
  TVector            operator *      (double           &Left    ,
                                      TVector          &Right   );
//-------------------------------------------------------------------------------------------------
  TVector            operator /      (double           &Right   );
  void               operator /=     (double           &Right   );
//-------------------------------------------------------------------------------------------------
  friend
  TVector            VectorProduct   (TVector          &Left    ,
                                      TVector          &Right   );
//-------------------------------------------------------------------------------------------------
  void               VectorProduct   (TVector          &Right   );
//-------------------------------------------------------------------------------------------------
  friend
  double             ScalarProduct   (TVector          &Left    ,
                                      TVector          &Right   );
//-------------------------------------------------------------------------------------------------
  friend
  double             abs             (TVector          &Vector  );
//-------------------------------------------------------------------------------------------------
};
//=================================================================================================
TVector        ::    TVector         (                          )
{
 x=0.0;
 y=0.0;
 z=0.0;
}
//-------------------------------------------------------------------------------------------------
TVector        ::    TVector         (TVector          &Original)
{
 x=Original.x;
 y=Original.y;
 z=Original.z;
}
//-------------------------------------------------------------------------------------------------
TVector        ::   ~TVector         (                          )
{
}
//-------------------------------------------------------------------------------------------------
TVector
TVector        ::    operator =      (TVector          &Original)
{
 x=Original.x;
 y=Original.y;
 z=Original.z;
 return *this;
}
//-------------------------------------------------------------------------------------------------
TVector
TVector        ::    operator +      (TVector          &Right   )
{
 TVector Result;
 Result.x=x+Right.x;
 Result.y=y+Right.y;
 Result.z=z+Right.z;
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TVector        ::    operator +=     (TVector          &Right   )
{
 x+=Right.x;
 y+=Right.y;
 z+=Right.z;
}
//-------------------------------------------------------------------------------------------------
TVector
TVector        ::    operator -      (TVector          &Right   )
{
 TVector Result;
 Result.x=x-Right.x;
 Result.y=y-Right.y;
 Result.z=z-Right.z;
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TVector        ::    operator -=     (TVector          &Right   )
{
 x-=Right.x;
 y-=Right.y;
 z-=Right.z;
}
//-------------------------------------------------------------------------------------------------
TVector
TVector        ::    operator *      (double           &Right   )
{
 TVector Result;
 Result.x=x*Right;
 Result.y=y*Right;
 Result.z=z*Right;
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TVector        ::    operator *=     (double           &Right   )
{
 x*=Right;
 y*=Right;
 z*=Right;
}
//-------------------------------------------------------------------------------------------------
TVector              operator *      (double           &Left    ,
                                      TVector          &Right   )
{
 TVector Result;
 Result.x=Left*Right.x;
 Result.y=Left*Right.y;
 Result.z=Left*Right.z;
 return Result;
}
//-------------------------------------------------------------------------------------------------
TVector
TVector        ::    operator /      (double           &Right   )
{
 TVector Result;
 Result.x=x/Right;
 Result.y=y/Right;
 Result.z=z/Right;
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TVector        ::    operator /=     (double           &Right   )
{
 x/=Right;
 y/=Right;
 z/=Right;
}
//-------------------------------------------------------------------------------------------------
TVector              VectorProduct   (TVector          &Left    ,
                                      TVector          &Right   )
{
 TVector Result;
 Result.x=Left.y*Right.z-Left.z*Right.y;
 Result.y=Left.z*Right.x-Left.x*Right.z;
 Result.z=Left.x*Right.y-Left.y*Right.x;
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TVector        ::    VectorProduct   (TVector          &Right   )
{
 TVector Result;
 Result.x=y*Right.z-z*Right.y;
 Result.y=z*Right.x-x*Right.z;
 Result.z=x*Right.y-y*Right.x;
 *this=Result;
}
//-------------------------------------------------------------------------------------------------
double               ScalarProduct   (TVector          &Left    ,
                                      TVector          &Right   )
{
 return (Left.x*Right.x+Left.y*Right.y+Left.z*Right.z);
}
//-------------------------------------------------------------------------------------------------
double               abs             (TVector          &Vector  )
{
 return sqrt(Vector.x*Vector.x+Vector.y*Vector.y+Vector.z*Vector.z);
}
//=================================================================================================
#endif // TVECTOR_HPP_INCLUDED
TMatixRow.hpp:
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
#ifndef TMATIXROW_HPP_INCLUDED
#define TMATIXROW_HPP_INCLUDED
//=================================================================================================
class TMatrixRow
{
//-------------------------------------------------------------------------------------------------
 protected:
//-------------------------------------------------------------------------------------------------
  double             Items[3];
//-------------------------------------------------------------------------------------------------
 public   :
//-------------------------------------------------------------------------------------------------
                     TMatrixRow      (                          );
                     TMatrixRow      (TMatrixRow       &Original);
//-------------------------------------------------------------------------------------------------
                    ~TMatrixRow      (                          );
//-------------------------------------------------------------------------------------------------
  TMatrixRow         operator =      (TMatrixRow       &Original);
//-------------------------------------------------------------------------------------------------
  double            &operator []     (size_t            Index   );
//-------------------------------------------------------------------------------------------------
};
//=================================================================================================
TMatrixRow     ::    TMatrixRow      (                          )
{
 Items[0]=0.0;
 Items[1]=0.0;
 Items[2]=0.0;
}
//-------------------------------------------------------------------------------------------------
TMatrixRow     ::    TMatrixRow      (TMatrixRow       &Original)
{
 Items[0]=Original.Items[0];
 Items[1]=Original.Items[1];
 Items[2]=Original.Items[2];
}
//-------------------------------------------------------------------------------------------------
TMatrixRow     ::   ~TMatrixRow      (                          )
{
}
//-------------------------------------------------------------------------------------------------
TMatrixRow
TMatrixRow     ::    operator =      (TMatrixRow       &Original)
{
 Items[0]=Original.Items[0];
 Items[1]=Original.Items[1];
 Items[2]=Original.Items[2];
 return *this;
}
//-------------------------------------------------------------------------------------------------
double              &
TMatrixRow     ::    operator []     (size_t            Index   )
{
 return Items[Index];
}
//=================================================================================================
#endif // TMATIXROW_HPP_INCLUDED
, TMatrix.hpp:
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
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
#ifndef TMATRIX_HPP_INCLUDED
#define TMATRIX_HPP_INCLUDED
//=================================================================================================
#include "TMatixRow.hpp"
//=================================================================================================
class TMatrix
{
//-------------------------------------------------------------------------------------------------
 protected:
//-------------------------------------------------------------------------------------------------
  TMatrixRow         Rows[3];
//-------------------------------------------------------------------------------------------------
 public   :
//-------------------------------------------------------------------------------------------------
                     TMatrix         (                          );
                     TMatrix         (TMatrix          &Original);
//-------------------------------------------------------------------------------------------------
                    ~TMatrix         (                          );
//-------------------------------------------------------------------------------------------------
  TMatrix            operator =      (TMatrix          &Original);
//-------------------------------------------------------------------------------------------------
  TMatrixRow        &operator []     (size_t            Index   );
//-------------------------------------------------------------------------------------------------
  TMatrix            operator +      (TMatrix          &Right   );
  void               operator +=     (TMatrix          &Right   );
//-------------------------------------------------------------------------------------------------
  TMatrix            operator -      (TMatrix          &Right   );
  void               operator -=     (TMatrix          &Right   );
//-------------------------------------------------------------------------------------------------
  TMatrix            operator *      (TMatrix          &Right   );
  void               operator *=     (TMatrix          &Right   );
//-------------------------------------------------------------------------------------------------
  TMatrix            operator *      (double           &Right   );
  void               operator *=     (double           &Right   );
//-------------------------------------------------------------------------------------------------
  friend
  TMatrix            operator *      (double           &Left    ,
                                      TMatrix          &Right   );
//-------------------------------------------------------------------------------------------------
  TMatrix            operator /      (double           &Right   );
  void               operator /=     (double           &Right   );
//-------------------------------------------------------------------------------------------------
  friend
  double             determinant     (TMatrix          &Matrix);
//-------------------------------------------------------------------------------------------------
  friend
  TMatrix            invert          (TMatrix          &Matrix  );
  void               invert          (                          );
//-------------------------------------------------------------------------------------------------
  friend
  TMatrix            transpose       (TMatrix          &Matrix  );
  void               transpose       (                          );
//-------------------------------------------------------------------------------------------------
  friend
  TVector            operator *      (TVector          &Vector  ,
                                      TMatrix          &Matrix  );
//-------------------------------------------------------------------------------------------------
  friend
  void               operator *=     (TVector          &Vector  ,
                                      TMatrix          &Matrix  );
//-------------------------------------------------------------------------------------------------
};
//=================================================================================================
TMatrix        ::    TMatrix         (                          )
{
 Rows[0][0]=1.0;
 Rows[0][1]=0.0;
 Rows[0][2]=0.0;
 Rows[1][0]=0.0;
 Rows[1][1]=1.0;
 Rows[1][2]=0.0;
 Rows[2][0]=0.0;
 Rows[2][1]=0.0;
 Rows[2][2]=1.0;
}
//-------------------------------------------------------------------------------------------------
TMatrix        ::    TMatrix         (TMatrix          &Original)
{
 Rows[0]=Original.Rows[0];
 Rows[1]=Original.Rows[1];
 Rows[2]=Original.Rows[2];
}
//-------------------------------------------------------------------------------------------------
TMatrix        ::   ~TMatrix         (                          )
{
 
}
//-------------------------------------------------------------------------------------------------
TMatrix
TMatrix        ::    operator =      (TMatrix          &Original)
{
 Rows[0]=Original.Rows[0];
 Rows[1]=Original.Rows[1];
 Rows[2]=Original.Rows[2];
 return *this;
}
//-------------------------------------------------------------------------------------------------
TMatrixRow          &
TMatrix        ::    operator []     (size_t            Index   )
{
 return Rows[Index];
}
//-------------------------------------------------------------------------------------------------
TMatrix
TMatrix        ::    operator +      (TMatrix          &Right   )
{
 TMatrix Result;
 Result[0][0]=(*this)[0][0]+Right[0][0];
 Result[0][1]=(*this)[0][1]+Right[0][1];
 Result[0][2]=(*this)[0][2]+Right[0][2];
 Result[1][0]=(*this)[1][0]+Right[1][0];
 Result[1][1]=(*this)[1][1]+Right[1][1];
 Result[1][2]=(*this)[1][2]+Right[1][2];
 Result[2][0]=(*this)[2][0]+Right[2][0];
 Result[2][1]=(*this)[2][1]+Right[2][1];
 Result[2][2]=(*this)[2][2]+Right[2][2];
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TMatrix        ::    operator +=     (TMatrix          &Right   )
{
 (*this)[0][0]+=Right[0][0];
 (*this)[0][1]+=Right[0][1];
 (*this)[0][2]+=Right[0][2];
 (*this)[1][0]+=Right[1][0];
 (*this)[1][1]+=Right[1][1];
 (*this)[1][2]+=Right[1][2];
 (*this)[2][0]+=Right[2][0];
 (*this)[2][1]+=Right[2][1];
 (*this)[2][2]+=Right[2][2];
}
//-------------------------------------------------------------------------------------------------
TMatrix
TMatrix        ::    operator -      (TMatrix          &Right   )
{
 TMatrix Result;
 Result[0][0]=(*this)[0][0]-Right[0][0];
 Result[0][1]=(*this)[0][1]-Right[0][1];
 Result[0][2]=(*this)[0][2]-Right[0][2];
 Result[1][0]=(*this)[1][0]-Right[1][0];
 Result[1][1]=(*this)[1][1]-Right[1][1];
 Result[1][2]=(*this)[1][2]-Right[1][2];
 Result[2][0]=(*this)[2][0]-Right[2][0];
 Result[2][1]=(*this)[2][1]-Right[2][1];
 Result[2][2]=(*this)[2][2]-Right[2][2];
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TMatrix        ::    operator -=     (TMatrix          &Right   )
{
 (*this)[0][0]-=Right[0][0];
 (*this)[0][1]-=Right[0][1];
 (*this)[0][2]-=Right[0][2];
 (*this)[1][0]-=Right[1][0];
 (*this)[1][1]-=Right[1][1];
 (*this)[1][2]-=Right[1][2];
 (*this)[2][0]-=Right[2][0];
 (*this)[2][1]-=Right[2][1];
 (*this)[2][2]-=Right[2][2];
}
//-------------------------------------------------------------------------------------------------
TMatrix
TMatrix        ::    operator *      (TMatrix          &Right   )
{
 TMatrix Result;
 Result[0][0]=(*this)[0][0]*Right[0][0]+(*this)[0][1]*Right[1][0]+(*this)[0][2]*Right[2][0];
 Result[0][1]=(*this)[0][0]*Right[0][1]+(*this)[0][1]*Right[1][1]+(*this)[0][2]*Right[2][1];
 Result[0][2]=(*this)[0][0]*Right[0][2]+(*this)[0][1]*Right[1][2]+(*this)[0][2]*Right[2][2];
 Result[1][0]=(*this)[1][0]*Right[0][0]+(*this)[1][1]*Right[1][0]+(*this)[1][2]*Right[2][0];
 Result[1][1]=(*this)[1][0]*Right[0][1]+(*this)[1][1]*Right[1][1]+(*this)[1][2]*Right[2][1];
 Result[1][2]=(*this)[1][0]*Right[0][2]+(*this)[1][1]*Right[1][2]+(*this)[1][2]*Right[2][2];
 Result[2][0]=(*this)[2][0]*Right[0][0]+(*this)[2][1]*Right[1][0]+(*this)[2][2]*Right[2][0];
 Result[2][1]=(*this)[2][0]*Right[0][1]+(*this)[2][1]*Right[1][1]+(*this)[2][2]*Right[2][1];
 Result[2][2]=(*this)[2][0]*Right[0][2]+(*this)[2][1]*Right[1][2]+(*this)[2][2]*Right[2][2];
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TMatrix        ::    operator *=     (TMatrix          &Right   )
{
 TMatrix Result;
 Result[0][0]=(*this)[0][0]*Right[0][0]+(*this)[0][1]*Right[1][0]+(*this)[0][2]*Right[2][0];
 Result[0][1]=(*this)[0][0]*Right[0][1]+(*this)[0][1]*Right[1][1]+(*this)[0][2]*Right[2][1];
 Result[0][2]=(*this)[0][0]*Right[0][2]+(*this)[0][1]*Right[1][2]+(*this)[0][2]*Right[2][2];
 Result[1][0]=(*this)[1][0]*Right[0][0]+(*this)[1][1]*Right[1][0]+(*this)[1][2]*Right[2][0];
 Result[1][1]=(*this)[1][0]*Right[0][1]+(*this)[1][1]*Right[1][1]+(*this)[1][2]*Right[2][1];
 Result[1][2]=(*this)[1][0]*Right[0][2]+(*this)[1][1]*Right[1][2]+(*this)[1][2]*Right[2][2];
 Result[2][0]=(*this)[2][0]*Right[0][0]+(*this)[2][1]*Right[1][0]+(*this)[2][2]*Right[2][0];
 Result[2][1]=(*this)[2][0]*Right[0][1]+(*this)[2][1]*Right[1][1]+(*this)[2][2]*Right[2][1];
 Result[2][2]=(*this)[2][0]*Right[0][2]+(*this)[2][1]*Right[1][2]+(*this)[2][2]*Right[2][2];
 *this=Result;
}
//-------------------------------------------------------------------------------------------------
TMatrix
TMatrix        ::    operator *      (double           &Right   )
{
 TMatrix Result;
 Result[0][0]=(*this)[0][0]*Right;
 Result[0][1]=(*this)[0][2]*Right;
 Result[0][2]=(*this)[0][1]*Right;
 Result[1][0]=(*this)[1][0]*Right;
 Result[1][1]=(*this)[1][2]*Right;
 Result[1][2]=(*this)[1][1]*Right;
 Result[2][0]=(*this)[2][0]*Right;
 Result[2][1]=(*this)[2][2]*Right;
 Result[2][2]=(*this)[2][1]*Right;
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TMatrix        ::    operator *=     (double           &Right   )
{
 (*this)[0][0]*=Right;
 (*this)[0][1]*=Right;
 (*this)[0][2]*=Right;
 (*this)[1][0]*=Right;
 (*this)[1][1]*=Right;
 (*this)[1][2]*=Right;
 (*this)[2][0]*=Right;
 (*this)[2][1]*=Right;
 (*this)[2][2]*=Right;
}
//-------------------------------------------------------------------------------------------------
TMatrix              operator *      (double           &Left    ,
                                      TMatrix          &Right   )
{
 TMatrix Result;
 Result[0][0]=Left*Right[0][0];
 Result[0][1]=Left*Right[0][1];
 Result[0][2]=Left*Right[0][2];
 Result[1][0]=Left*Right[1][0];
 Result[1][1]=Left*Right[1][1];
 Result[1][2]=Left*Right[1][2];
 Result[2][0]=Left*Right[2][0];
 Result[2][1]=Left*Right[2][1];
 Result[2][2]=Left*Right[2][2];
 return Result;
}
//-------------------------------------------------------------------------------------------------
TMatrix
TMatrix        ::    operator /      (double           &Right   )
{
 TMatrix Result;
 Result[0][0]=(*this)[0][0]/Right;
 Result[0][1]=(*this)[0][2]/Right;
 Result[0][2]=(*this)[0][1]/Right;
 Result[1][0]=(*this)[1][0]/Right;
 Result[1][1]=(*this)[1][2]/Right;
 Result[1][2]=(*this)[1][1]/Right;
 Result[2][0]=(*this)[2][0]/Right;
 Result[2][1]=(*this)[2][2]/Right;
 Result[2][2]=(*this)[2][1]/Right;
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TMatrix        ::    operator /=     (double           &Right   )
{
 (*this)[0][0]/=Right;
 (*this)[0][1]/=Right;
 (*this)[0][2]/=Right;
 (*this)[1][0]/=Right;
 (*this)[1][1]/=Right;
 (*this)[1][2]/=Right;
 (*this)[2][0]/=Right;
 (*this)[2][1]/=Right;
 (*this)[2][2]/=Right;
}
//-------------------------------------------------------------------------------------------------
double               determinant     (TMatrix          &Matrix)
{
 return Matrix[0][0]*(Matrix[1][1]*Matrix[2][2]-Matrix[1][2]*Matrix[2][1])-Matrix[0][1]*(Matrix[1][0]*Matrix[2][2]-Matrix[1][2]*Matrix[2][0])+Matrix[2][1]*(Matrix[1][0]*Matrix[2][1]-Matrix[1][1]*Matrix[2][0]);
}
//-------------------------------------------------------------------------------------------------
TMatrix              invert          (TMatrix          &Matrix  )
{
 TMatrix Result;
 double det;
 det=determinant(Matrix);
 Result[0][0]=(Matrix[1][1]*Matrix[2][2]-Matrix[1][2]*Matrix[2][1])/det;
 Result[0][1]=(Matrix[1][2]*Matrix[2][0]-Matrix[1][0]*Matrix[2][2])/det;
 Result[0][2]=(Matrix[1][0]*Matrix[2][1]-Matrix[1][1]*Matrix[2][0])/det;
 Result[1][0]=(Matrix[0][2]*Matrix[2][1]-Matrix[0][1]*Matrix[2][2])/det;
 Result[1][1]=(Matrix[0][0]*Matrix[2][2]-Matrix[0][2]*Matrix[2][0])/det;
 Result[1][2]=(Matrix[0][1]*Matrix[2][0]-Matrix[0][0]*Matrix[2][1])/det;
 Result[2][0]=(Matrix[0][1]*Matrix[1][2]-Matrix[0][2]*Matrix[1][1])/det;
 Result[2][1]=(Matrix[0][2]*Matrix[1][0]-Matrix[0][0]*Matrix[1][2])/det;
 Result[2][2]=(Matrix[0][0]*Matrix[1][1]-Matrix[0][1]*Matrix[1][0])/det;
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TMatrix        ::    invert          (                          )
{
 TMatrix Result;
 double det;
 det=determinant(*this);
 Result[0][0]=((*this)[1][1]*(*this)[2][2]-(*this)[1][2]*(*this)[2][1])/det;
 Result[0][1]=((*this)[1][2]*(*this)[2][0]-(*this)[1][0]*(*this)[2][2])/det;
 Result[0][2]=((*this)[1][0]*(*this)[2][1]-(*this)[1][1]*(*this)[2][0])/det;
 Result[1][0]=((*this)[0][2]*(*this)[2][1]-(*this)[0][1]*(*this)[2][2])/det;
 Result[1][1]=((*this)[0][0]*(*this)[2][2]-(*this)[0][2]*(*this)[2][0])/det;
 Result[1][2]=((*this)[0][1]*(*this)[2][0]-(*this)[0][0]*(*this)[2][1])/det;
 Result[2][0]=((*this)[0][1]*(*this)[1][2]-(*this)[0][2]*(*this)[1][1])/det;
 Result[2][1]=((*this)[0][2]*(*this)[1][0]-(*this)[0][0]*(*this)[1][2])/det;
 Result[2][2]=((*this)[0][0]*(*this)[1][1]-(*this)[0][1]*(*this)[1][0])/det;
 *this=Result;
}
//-------------------------------------------------------------------------------------------------
TMatrix              transpose       (TMatrix          &Matrix  )
{
 TMatrix Result;
 Result[0][0]=Matrix[0][0];
 Result[0][1]=Matrix[1][0];
 Result[0][2]=Matrix[2][0];
 Result[1][0]=Matrix[0][1];
 Result[1][1]=Matrix[1][1];
 Result[1][2]=Matrix[2][1];
 Result[2][0]=Matrix[0][2];
 Result[2][1]=Matrix[1][2];
 Result[2][2]=Matrix[2][2];
 return Result;
}
//-------------------------------------------------------------------------------------------------
void
TMatrix        ::    transpose       (                          )
{
TMatrix Result;
 Result[0][0]=(*this)[0][0];
 Result[0][1]=(*this)[1][0];
 Result[0][2]=(*this)[2][0];
 Result[1][0]=(*this)[0][1];
 Result[1][1]=(*this)[1][1];
 Result[1][2]=(*this)[2][1];
 Result[2][0]=(*this)[0][2];
 Result[2][1]=(*this)[1][2];
 Result[2][2]=(*this)[2][2];
 *this=Result;
}
//-------------------------------------------------------------------------------------------------
TVector              operator *      (TVector          &Vector  ,
                                      TMatrix          &Matrix  )
{
 TVector Result;
 Result.x=Vector.x*Matrix[0][0]+Vector.y*Matrix[1][0]+Vector.z*Matrix[2][0];
 Result.y=Vector.x*Matrix[0][1]+Vector.y*Matrix[1][1]+Vector.z*Matrix[2][1];
 Result.z=Vector.x*Matrix[0][2]+Vector.y*Matrix[1][2]+Vector.z*Matrix[2][2];
 return Result;
}
//-------------------------------------------------------------------------------------------------
void                 operator *=     (TVector          &Vector  ,
                                      TMatrix          &Matrix  )
{
 TVector Result;
 Result.x=Vector.x*Matrix[0][0]+Vector.y*Matrix[1][0]+Vector.z*Matrix[2][0];
 Result.y=Vector.x*Matrix[0][1]+Vector.y*Matrix[1][1]+Vector.z*Matrix[2][1];
 Result.z=Vector.x*Matrix[0][2]+Vector.y*Matrix[1][2]+Vector.z*Matrix[2][2];
 Vector=Result;
}
//=================================================================================================
#endif // TMATRIX_HPP_INCLUDED
, TOrientation:
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 TORIENTATION_HPP_INCLUDED
#define TORIENTATION_HPP_INCLUDED
//=================================================================================================
#include "TMatrix.hpp"
//=================================================================================================
class TOrientation
{
//-------------------------------------------------------------------------------------------------
 public   :
//-------------------------------------------------------------------------------------------------
  TMatrix            TurnMatrix;
//-------------------------------------------------------------------------------------------------
                     TOrientation    (                          );
                     TOrientation    (TOrientation     &Original);
//-------------------------------------------------------------------------------------------------
                    ~TOrientation    (                          );
//-------------------------------------------------------------------------------------------------
  TOrientation       operator =      (TOrientation     &Original);
//-------------------------------------------------------------------------------------------------
};
//=================================================================================================
TOrientation   ::    TOrientation    (                          )
{
 
}
//-------------------------------------------------------------------------------------------------
TOrientation   ::    TOrientation    (TOrientation     &Original)
{
 TurnMatrix=Original.TurnMatrix;
}
//-------------------------------------------------------------------------------------------------
TOrientation   ::   ~TOrientation    (                          )
{
 
}
//-------------------------------------------------------------------------------------------------
TOrientation
TOrientation   ::    operator =      (TOrientation     &Original)
{
 TurnMatrix=Original.TurnMatrix;
 return *this;
}
//=================================================================================================
#endif // TORIENTATION_HPP_INCLUDED
TBone.hpp:
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
#ifndef TBONE_HPP_INCLUDED
#define TBONE_HPP_INCLUDED
//=================================================================================================
#include <string>
//=================================================================================================
#include "TVector.hpp"
#include "TOrientation.hpp"
#include "TArray.hpp"
//=================================================================================================
class TBone
{
//-------------------------------------------------------------------------------------------------
 public   :
//-------------------------------------------------------------------------------------------------
  TBone             *Parent;
  TOrientation       Orientation;
  TVector            Position;
  std::string        Name;
//-------------------------------------------------------------------------------------------------
  TArray <TBone>     Childs;
//-------------------------------------------------------------------------------------------------
                     TBone           (                          );
                     TBone           (TBone            &Original);
//-------------------------------------------------------------------------------------------------
                    ~TBone           (                          );
//-------------------------------------------------------------------------------------------------
  TBone              operator =      (TBone            &Original);
//-------------------------------------------------------------------------------------------------
};
//=================================================================================================
TBone          ::    TBone           (                          )
{
 Parent=NULL;
 Name  ="";
}
//-------------------------------------------------------------------------------------------------
TBone          ::    TBone           (TBone            &Original)
{
 Parent     =Original.Parent;
 Orientation=Original.Orientation;
 Position   =Original.Position;
 Name       =Original.Name;
 Childs     =Original.Childs;
}
//-------------------------------------------------------------------------------------------------
TBone          ::   ~TBone           (                          )
{
}
//-------------------------------------------------------------------------------------------------
TBone
TBone          ::    operator =      (TBone            &Original)
{
 Parent     =Original.Parent;
 Orientation=Original.Orientation;
 Position   =Original.Position;
 Name       =Original.Name;
 Childs     =Original.Childs;
 return *this;
}
//=================================================================================================
#endif // TBONE_HPP_INCLUDED
.Вот такая вот коряга дерево моей мечты.
Джек
5 / 5 / 0
Регистрация: 16.08.2011
Сообщений: 77
29.11.2012, 09:36  [ТС]     Как вы учили деревья #12
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А по сути: прохода в глубину дерева нет вообще: элемент добавляется или в корень->справа или в корень->слева или в сам корень.
четвёртого видимо не дано.
А как сделать проход в глубину дерева? Можете обьяснить как это сделатьДобавлено через 7 минут
Извените. Недавно изучаю деревья поэтому прошу что то по проще чтобы понять простое а потом и модернизировать и импровизироввать.

Добавлено через 5 минут
Вот такая вот коряга дерево моей мечты.[/QUOTE]

Простите. А можно что то проще сам код хорош но недавно изучаю деревья поэтому прошу что то близкое к элементарному.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
29.11.2012, 10:46     Как вы учили деревья #13
Деревья рекурсивны, если правый потомок уже существует, а уровней может быть больше двух, то при x>root->data надо спустить добавление в поддерево:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
protected: void add(Node *&root, int x)
{
 Node *r=new Node;
 r->data=x
 if (root==NULL)
 {
  root=r;
  return;
 }
 if (x>root->data)
 {
  add(root->right, x);
  return;
 }
 add(root->left, x);
}
public: void add(int x)
{
  add(root, x);
}
Добавлено через 1 час 7 минут
Цитата Сообщение от Джек Посмотреть сообщение
сам код хорош
Нет, он коряво-велосипедистый. Я ведь не зря обозвал это дерево корягой.
Джек
5 / 5 / 0
Регистрация: 16.08.2011
Сообщений: 77
30.11.2012, 00:59  [ТС]     Как вы учили деревья #14
Цитата Сообщение от taras atavin Посмотреть сообщение
add(root->right, x);
Оно должно возвращаться?

и
Цитата Сообщение от taras atavin Посмотреть сообщение
Node *&root
Я так понимаю указатель на адрес элемента Node?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
30.11.2012, 05:58     Как вы учили деревья #15
Для того, чтоб понять деревья, нужно для начала понять суть рекурсии, ну а далее - самый мудрый совет дал go, все через это проходили. Палочки и кружочки с циферками) Также, про деревья написано у Кнута (Искусство программирования). Когда я программировал АВЛ-деревья, читал еще Вирта Н. "Алгоритмы и структуры данных".

Добавлено через 2 минуты

Не по теме:

taras atavin, оформление кода конечно ацкое.

taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.11.2012, 11:28     Как вы учили деревья #16
Цитата Сообщение от Джек Посмотреть сообщение
Я так понимаю указатель на адрес элемента Node?
Нет. Ссылка на указатель. То есть на самом деле двойной указатель, но внутри метода синтаксически маскируется под простой.

Добавлено через 2 минуты
Цитата Сообщение от MrGluck Посмотреть сообщение
Для того, чтоб понять деревья, нужно для начала понять суть рекурсии, ну а далее - самый мудрый совет дал go, все через это проходили. Палочки и кружочки с циферками) Также, про деревья написано у Кнута (Искусство программирования). Когда я программировал АВЛ-деревья, читал еще Вирта Н. "Алгоритмы и структуры данных".
Я свою корягу без бумаги написал. И вообще ни разу не брался за бумагу до написания проги, или внесения в неё изменений, а только когда прога полностью готова.
Джек
5 / 5 / 0
Регистрация: 16.08.2011
Сообщений: 77
30.11.2012, 23:59  [ТС]     Как вы учили деревья #17
Приношу массу извинений но код не возвращает и не выводит ничего, а вот деструктор то он будет позднее.


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
//---------------------------------------------------------------------------
 
#pragma hdrstop
#include <iostream.h>
#include <conio.h>
 
 
//---------------------------------------------------------------------------
 
#pragma argsused
class Tree
{private:
struct Node
{Node *left;
Node *right;
int data;
Node(){left=right=0;data=0;}
};
public:
Node *root;
Tree(){root=0;}
protected: void add(Node *&root, int x)
{
 Node *r=new Node;
 r->data=x;
 if (root==NULL)
 {
  root=r;
  return;
 }
 if (x>root->data)
 {
  add(root->right, x);
  return;
 }
 add(root->left, x);
}
public: void add(int x)
{
  add(root, x);
}
};
int main()
{
Tree j;
j.add(2);
j.add(4);
getch();
return 0;
}
//---------------------------------------------------------------------------
что не так?

Добавлено через 3 часа 16 минут
А вроди нашел почему не выводился результат что то вроде получилось но правильно или нет подскажите плииз правильно или нет.

Вот еще код:

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
//---------------------------------------------------------------------------
 
#pragma hdrstop
#include <iostream.h>
#include <conio.h>
 
 
//---------------------------------------------------------------------------
 
#pragma argsused
class Tree
{private:
struct Node
{Node *left;
Node *right;
int data;
Node(){left=right=0;data=0;}
};
public:
Node *root;
Tree(){root=0;}
protected: void add(Node *&root, int x)
{
 Node *r=new Node;
 r->data=x;
 if (root==NULL)
 {
  root=r;
  return;
 }
 if (x>root->data)
 {
  add(root->right, x);
  return;
 }
 add(root->left, x);
}
public: int add(int x)
{
add(root, x);
return x;
}
};
int main()
{
Tree t;
cout<<t.add(2)<<'\n';
cout<<t.add(4)<<'\n';
getch();
return 0;
}
//---------------------------------------------------------------------------
dikanev
21 / 21 / 1
Регистрация: 28.05.2010
Сообщений: 67
01.12.2012, 01:21     Как вы учили деревья #18
Минимальные необходимые сведения о деревьях можно почерпнуть, например, в данной статье про рекурсивные алгоритмы. Ну, и первый том Кнута можно почитать.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
01.12.2012, 01:27     Как вы учили деревья #19
Нашел свою лабу тогдашнюю по деревьям.
Мб полезно будет, но я тогда С++ изучал чуть более чем полгода.
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
#include <iostream>
#include <conio.h>
#include <fstream>
using namespace std;
 
struct  bin_tree
{
   int value;
   bin_tree *left, *right;
}*pHead = NULL; // указатель на вершину равен нулю
 
// добавление конкретного узла дерева
void add_node(bin_tree*, int); 
// проверка на "пустоту" дерева, если указатель на вершину равен нулю, создает узел
void add_bin_tree(int);
// обход
void print(bin_tree*);
void traversal(bin_tree*, ofstream&);
int h_tree(bin_tree *);
 
int main()
{
    setlocale (LC_ALL, "Russian");
    int choose, el;
    cout<< "1. Загрузить последовательность с файла\n"
        << "2. Ввести последовательность вручную\n\n"
        << "Ваш выбор: ";
    do{ cin>> choose;} while(choose != 1 && choose != 2);
    if (choose == 1)
    {        
        ifstream iz("bin.txt");
        if (iz.bad()) return 1;
        while(!iz.eof() && iz>> el)
            add_bin_tree (el);     
        iz.close();
    }
    
    if (choose == 2)
    {
        cout<< "Информационные поля вершин дерева:\n";
        while(cin>> el)
            add_bin_tree (el);
    }
    ofstream o("bin.txt");
    print (pHead);
    traversal (pHead, o);
    getch();
    o.close();
    return 0;
}
 
void add_node(bin_tree* tree, int value) // добавление конкретного узла дерева
{
    if(value < tree->value)
    { 
        if(tree->left != NULL) // если значение меньше, двигаемся по "левой ветке"
            add_node(tree->left, value);
        else
        {  
            tree->left = new bin_tree;
            tree->left->value = value;
            tree->left->left = NULL;
            tree->left->right = NULL;
        }
    }
 
    if(value > tree->value) // иначе двигаемся по правой 
    { 
        if(tree->right != NULL)
            add_node(tree->right, value);
        else
        {
            tree->right = new bin_tree;
            tree->right->value = value;
            tree->right->left=NULL;
            tree->right->right=NULL;
        }
    }
 
    if(value == tree->value)                
        cout<< value<< " is already in tree"<< endl;
}
 
void add_bin_tree(int value)
{
    if(pHead == NULL) // если дерево пустое - создадим первый узел
    {
       pHead = new bin_tree;
       pHead->value = value;
       pHead->left = NULL;
       pHead->right = NULL;
    }
    else
        add_node(pHead, value); // если в вершине уже что-то есть - добавляем слева или справа 
}
 
void traversal(bin_tree* tree, ofstream &o)
{     
    if (tree != NULL)
    { 
        traversal(tree->left, o);
        o<< tree->value<< " ";
        traversal(tree->right, o);
    }
}
 
void print(bin_tree* tree)
{     
    if (tree != NULL)
    { 
        print(tree->left);
        cout<< tree->value<< " ";
        print(tree->right);
    }
}
 
int h_tree(bin_tree* tree)
{
     int h = 1, m = 0, s;
     if (tree == NULL)
        return 0;
     s = h_tree(tree->left);
     if (s > m)
         m = s;
     s = h_tree(tree->right);
     if (s > m)
         m = s;
     return h + m;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2012, 18:17     Как вы учили деревья
Еще ссылки по теме:

Деревья C++
Как разобраться с тем, что такое указатели, стеки, деревья? C++
Деревья C++

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

Или воспользуйтесь поиском по форуму:
Джек
5 / 5 / 0
Регистрация: 16.08.2011
Сообщений: 77
05.12.2012, 18:17  [ТС]     Как вы учили деревья #20
Вот код но некоторые момнты (в коментах) не понял обьясните пожалуйста. И проверьте правильно ли в коментах остальное если можно.

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
//---------------------------------------------------------------------------
 
#pragma hdrstop
#include <iostream.h>
#include <conio.h>
 
 
#include <tchar.h>
//---------------------------------------------------------------------------
 
#pragma argsused
struct node                   //наша струра
{node *left;                //указатель на левый узел
node *right;                   //указатель на правыйузел
int data;                      //даные
 
};
node *root=NULL;              //никакого узла небыло создано петому указатель на корень 0
void add(node **r,int d)         //node **r - указатель на корневой указатель int d - даные
{
if((*r)==NULL)      //если укзатель елемент структруы == 0,
 
                        //а так оно и есть по тому что мы его просто обявили
 
{(*r)=new node;   //создаем указатель на новый елемнт структуры
 
                         //(то есть выделяем память под новый указатель)
 
(*r)->data=d;             //это будет данным числом корнеаого елемента таким образом
                              //получаеться мы корневому елемнту задаем значение на которое он указывает
 
(*r)->left=(*r)->right=NULL;           //присваиваем указателям нулевые адреса по скольку
                                //по скольку больше никаких даных не добавлялось то это начальние адреса
return; //ето выход из if-a
}
if(d>(*r)->data)add(&(*r)->left,d);//проверяем значение, указатель указывает
                               //на адрес этого значения
 
else
 
add(&(*r)->left,d);     //аналогично
}
void print(node *n,int d)     //печать здесь просто указатель по скольку не производиться
                              //смена указателя
 
{if(n==NULL)              //если етот указатель больше ниначто не указывает,то
 
return;                        //выходим
 
else
 
{print(n->left,d);              //рекурсивный вызов
 
cout<<n->data<<endl;     //вывод всех даных.
 
}
 
print(n->right,++d);
 
}
 
int main()
{    int n,s;
cin>>n;
for(int i=0;i<n;i++)
{cin>>s;
add(&root,s);                     //передаем даные, то есть корневым елементом будет первый введёный
                                        //елемнт в цыкле.
}
print(root,0); /вот только почему здесь 0 есть? 
getch();
    return 0;
}
//---------------------------------------------------------------------------
Yandex
Объявления
05.12.2012, 18:17     Как вы учили деревья
Ответ Создать тему
Опции темы

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