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

АВЛ дерево - C++

Восстановить пароль Регистрация
 
Andrariel
0 / 0 / 0
Регистрация: 02.05.2015
Сообщений: 2
01.10.2016, 15:32     АВЛ дерево #1
Здравствуйте. Я начинающий программист и мне нужна помощь. Сейчас пытаюсь понять тему АВЛ деревьев и попробовала забить этот код, но к сожалению он не компилирует. Подскажите, где здесь ошибка? (код из методички, вот и не понимаю, что не так)
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
#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
#include <malloc.h> 
#include <time.h> 
#include <Windows.h>  
typedef int ElementType; 
typedef struct AvlNode *Position; 
typedef struct AvlNode *AvlTree;  
struct AvlNode 
{             
ElementType Element;             
AvlTree Left;             
AvlTree Right;             
int Height;         };  
AvlTree MakeEmpty( AvlTree T ); 
Position Find( ElementType X, AvlTree T ); 
Position FindMin( AvlTree T ); 
Position FindMax( AvlTree T ); 
AvlTree Insert( ElementType X, AvlTree T ); 
ElementType Retrieve( Position P ); 
void printTree(AvlTree T, int l = 0); //функция удаления вершины и ее поддеревьев 
AvlTree MakeEmpty( AvlTree T )  
{   if( T != NULL )   
{     MakeEmpty( T->Left );     
MakeEmpty( T->Right );     
free( T );   }   
  return NULL; }  // поиск вершины со значением X 
  Position Find( ElementType X, AvlTree T ) 
  {   if( T == NULL )     
  return NULL;     
  if( X < T->Element )       
  return Find( X, T->Left );     
  else       
  if( X > T->Element )         
  return Find( X, T->Right );       
  else         
  return T; }  
//функция поиска вершины с минимальным значением 
Position FindMin( AvlTree T ) 
{   if( T == NULL )     
return NULL;   
else     
if( T->Left == NULL )       
return T;     
else       
return FindMin( T->Left ); }  
//функция поиска вершины с максимальным значением 
Position FindMax( AvlTree T )  
{   if( T != NULL )     
while( T->Right != NULL )       
T = T->Right;   
return T; }  
//функция возвращает вес вершины  
int Height( Position P ) 
{   if( P == NULL )     
return -1;   
else     
return P->Height;   
}  
//функция возвращает максимальное из двух чисел 
int Max( int Lhs, int Rhs )  
{  if(Lhs > Rhs)   
return Lhs;   
return Rhs; }  
/*функция выполняет правый поворот между вершиной K2 и ее левым потомком*/ 
Position SingleRotateWithLeft( Position K2 ) 
{   Position K1;   
K1 = K2->Left;//записываем левый указатель на потомка дерева   
K2->Left = K1->Right;   
K1->Right = K2;   
K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;  
K1->Height = Max( Height( K1->Left ), K2->Height ) + 1;   
return K1;  //Новый корень 
}  
/*функция выполняет левый поворот между вершиной K1 и ее правым потомком*/ 
Position SingleRotateWithRight( Position K1 ) 
{   Position K2;   
K2 = K1->Right;/*записываем правый указатель на потомка дерева*/   
K1->Right = K2->Left;   
K2->Left = K1;   
K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;   
K2->Height = Max( Height( K2->Right ), K1->Height ) + 1;   
return K2;  //новый корень 
}  
//функция выполняет двойной лево-правый поворот 
Position DoubleRotateWithLeft( Position K3 ) 
{   // поворот между K1 и K2/   
K3->Left = SingleRotateWithRight( K3->Left );   // поворот между K3 и K2   
return SingleRotateWithLeft( K3 );   
}  
//функция выполняет двойной право-левый поворот  
Position DoubleRotateWithRight( Position K1 ) 
{   // поворот между K3 и K2   
K1->Right = SingleRotateWithLeft( K1->Right );   // поворот между K1 и K2   
return SingleRotateWithRight( K1 ); }  
//функция вставки вершины в АВЛ-дерево 
AvlTree Insert( ElementType X, AvlTree T )
{   if( T == NULL )   
{     T = (AvlTree) malloc(sizeof(AvlNode));     
if( T == NULL )       
printf("Недостаточно памяти!!!\n" );     
else {       T->Element = X; T->Height = 0;       
T->Left = T->Right = NULL;     }   }   
else if( X < T->Element ) 
{     T->Left = Insert( X, T->Left );     
if( Height( T->Left ) - Height( T->Right ) == 2 )       
if( X < T->Left->Element )         
T = SingleRotateWithLeft( T );       
else         
T = DoubleRotateWithLeft( T );   
}   
else if( X > T->Element ) 
{     
T->Right = Insert( X, T->Right );       
if( Height( T->Right ) - Height( T->Left ) == 2 )         
if( X > T->Right->Element )           
T = SingleRotateWithRight( T );         
else           
T = DoubleRotateWithRight( T );   
}   
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;   
return T; 
}    
//функция возвращает значение, хранящееся в вершине 
ElementType Retrieve( Position P ) 
{   return P->Element; }  
//функция вывода АВЛ-дерева на печать 
void printTree(AvlTree T, int l)
{   
int i;   
if ( T != NULL ) 
{     
printTree(T->Right, l+1);     
for (i=0; i < l; i++)   
printf("    ");     
printf ("%4ld", Retrieve ( T ));     
printTree(T->Left, l+1);   
}   
else printf("\n"); 
}  
void main() 
{  
SetConsoleCP(1251);     
SetConsoleOutputCP(1251);  
int i, *a, maxnum;   
AvlTree T;     
Position P;     
int j = 0;   
printf("Введите количество элементов maxnum : ");   
scanf("%d",&maxnum); printf("\n");     
a = (int*) malloc(sizeof(int)*maxnum);   
srand(time(NULL)*1000);   // генерация массива   
for (i = 0; i < maxnum; i++)     
a[i] = rand()%100;   
printf("Вывод сгенерированной последовательности\n");   
for (i = 0; i < maxnum; i++)     
printf("%d \n\n",a[i]);      // добавление элементов в АВЛ-дерево     
T = MakeEmpty( NULL );   
for( i = 0; i < maxnum; i++ )         
T = Insert( a[i], T );   
printf("Вывод АВЛ-дерева\n");   
printTree(T);   
  printf("\nВведите вершину для поиска\n");   
  int temp; 
  scanf("%d",&temp);   
  Position Temp_node=NULL;   //поиск вершины с заданным номером temp  
Temp_node = Find(temp,T);   
if (Temp_node!=NULL)   
printf("\nВершина %d найдена\n",Temp_node->Element);   
else    
printf("\nТакой вершины нет!\n");   
getch();   
printf("\nMin = %d, Max = %d\n", 
Retrieve(FindMin(T)),  
Retrieve(FindMax(T)));   // удаление АВЛ-дерева   
T = MakeEmpty(T);   
free(a);   
getch();  
return; }
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2016, 15:32     АВЛ дерево
Посмотрите здесь:

C++ Дерево
Как в АВЛ-дереве найти самую короткую ветвь и удалить ее? C++
Высота авл дерева - как считать? C++
АВЛ дерево и коллизия хэша C++
C++ АВЛ-дерево
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Новичок
Модератор
 Аватар для Новичок
1141 / 712 / 148
Регистрация: 17.07.2012
Сообщений: 4,043
Записей в блоге: 1
Завершенные тесты: 2
01.10.2016, 15:55     АВЛ дерево #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Andrariel Посмотреть сообщение
void main()
Убить автора методички.
gazlan
2863 / 1811 / 272
Регистрация: 27.08.2010
Сообщений: 4,908
Записей в блоге: 1
01.10.2016, 19:47     АВЛ дерево #3
К слову, несмотря на омерзительный стиль, компилируется.
Код
C:\TEMP\t\t.cpp(162) : warning C4101: 'P' : unreferenced local variable
C:\TEMP\t\t.cpp(163) : warning C4189: 'j' : local variable is initialized but not referenced
Linking...

t.exe - 0 error(s), 2 warning(s)
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
01.10.2016, 20:01     АВЛ дерево #4
Может топикстартер ещё не понял, поэтому намекну, что код очень плохо читается и отбивает желание помочь.
Andrariel
0 / 0 / 0
Регистрация: 02.05.2015
Сообщений: 2
02.10.2016, 10:59  [ТС]     АВЛ дерево #5
Короче, придётся мне найти другую методичку по Си++
Yandex
Объявления
02.10.2016, 10:59     АВЛ дерево
Ответ Создать тему
Опции темы

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