Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Andrariel
0 / 0 / 0
Регистрация: 02.05.2015
Сообщений: 2
1

АВЛ дерево

01.10.2016, 15:32. Просмотров 1171. Ответов 4
Метки нет (Все метки)

Здравствуйте. Я начинающий программист и мне нужна помощь. Сейчас пытаюсь понять тему АВЛ деревьев и попробовала забить этот код, но к сожалению он не компилирует. Подскажите, где здесь ошибка? (код из методички, вот и не понимаю, что не так)
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; }
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2016, 15:32
Ответы с готовыми решениями:

АВЛ-дерево
Из входной последовательности символов построить АВЛ-дерево без повторов. Найти...

АВЛ дерево и коллизия хэша
До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые...

Высота авл дерева - как считать?
Добрый вечер. Забавно. Предположим, что пустой указатель равен -1, высота пр...

Комменты к реализации Красно-черного и АВЛ дерева
Люди добрые помогите разобрать и по возможности написать комментарии к этим 2м...

Как в АВЛ-дереве найти самую короткую ветвь и удалить ее?
Доброго времени суток. Нужна помощь. В АВЛ-дереве надо найти самую короткую...

4
Новичок
Модератор
1511 / 979 / 465
Регистрация: 17.07.2012
Сообщений: 4,969
Завершенные тесты: 3
01.10.2016, 15:55 2
Лучший ответ Сообщение было отмечено Andrariel как решение

Решение

Цитата Сообщение от Andrariel Посмотреть сообщение
void main()
Убить автора методички.
1
gazlan
3141 / 1917 / 311
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 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)
0
Kuzia domovenok
2436 / 2144 / 523
Регистрация: 25.03.2012
Сообщений: 7,724
Записей в блоге: 1
01.10.2016, 20:01 4
Может топикстартер ещё не понял, поэтому намекну, что код очень плохо читается и отбивает желание помочь.
0
Andrariel
0 / 0 / 0
Регистрация: 02.05.2015
Сообщений: 2
02.10.2016, 10:59  [ТС] 5
Короче, придётся мне найти другую методичку по Си++
0
02.10.2016, 10:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2016, 10:59

Добрый день, читал на хабре про АВЛ-деревья и хотелось бы кое-что уточнить
Добрый день, читал на хабре про АВЛ-деревья и возник один вопрос вот ссылка...

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

Дано дерево. Распечатать дерево по уровням
Дано дерево. Распечатать дерево по уровням.


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

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

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