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

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

Войти
Регистрация
Восстановить пароль
 
Andrariel
0 / 0 / 0
Регистрация: 02.05.2015
Сообщений: 2
#1

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

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

АВЛ-дерево - C++
Из входной последовательности символов построить АВЛ-дерево без повторов. Найти в нем узел, относительно которого будет максимальная...

АВЛ дерево и коллизия хэша - C++
До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые структуры, позволяющие сделать нечто вида: printf(&quot;%d\n&quot;,...

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

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

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

Добрый день, читал на хабре про АВЛ-деревья и хотелось бы кое-что уточнить - C++
Добрый день, читал на хабре про АВЛ-деревья и возник один вопрос вот ссылка на статью http://habrahabr.ru/post/150732/ Не могли бы Вы...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Новичок
Модератор
1195 / 766 / 164
Регистрация: 17.07.2012
Сообщений: 4,174
Записей в блоге: 1
Завершенные тесты: 2
01.10.2016, 15:55     АВЛ дерево #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Andrariel Посмотреть сообщение
void main()
Убить автора методички.
gazlan
3130 / 1905 / 285
Регистрация: 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)
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
01.10.2016, 20:01     АВЛ дерево #4
Может топикстартер ещё не понял, поэтому намекну, что код очень плохо читается и отбивает желание помочь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2016, 10:59     АВЛ дерево
Еще ссылки по теме:

N-дерево - C++
Дано N-дерево. Найти поддерево не включающее ни одну из заданных вершин. Вообще хотя бы &quot;Дано N-дерево&quot; - если вы кинете готовый код...

дерево - C++
// derevo_lr2.cpp : Defines the entry point for the console application. #include &quot;stdafx.h&quot; #include &quot;iostream&quot; using namespace std;...

Дерево - C++
Нужно НЕ рекурсивно распечатать двоичное дерево по слоям, собственно как это сделать?

B-дерево - C++
Есть у кого реализация B-дерева на Си? хотя бы добавление и удаление)))) А то есть на Паскале, но перевести это для меня нереально)

Дерево... - C++
в общем есть дерево двоичного поиска, состоит из функций добавления, удаления, поиска, вывода, ф-ция, которая выводит размер дерева... К...

Дерево - C++
Условие: Программа построения дерева, где узел(корень) - ФИО препода, а инф. поля (наверное левая\правая ветки) имеют записи:...


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

Или воспользуйтесь поиском по форуму:
Andrariel
0 / 0 / 0
Регистрация: 02.05.2015
Сообщений: 2
02.10.2016, 10:59  [ТС]     АВЛ дерево #5
Короче, придётся мне найти другую методичку по Си++
Yandex
Объявления
02.10.2016, 10:59     АВЛ дерево
Ответ Создать тему
Опции темы

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