Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.65
Anastasiya1
0 / 0 / 0
Регистрация: 21.03.2013
Сообщений: 77
#1

Создание бинарного дерева поиска - C++

16.04.2013, 17:25. Просмотров 3078. Ответов 16
Метки нет (Все метки)

Людииииии помогите пож-таааа.....Нужно создать бинарное дерево поиска, считывая элементы из текст файла..
Очень нужноооо кто нибудь

Добавлено через 47 минут
Ну кто нибудь
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.04.2013, 17:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Создание бинарного дерева поиска (C++):

Создание бинарного дерева из бинарного файла - C++
struct Bin { string name; string city; int players; int score; }; void ReadFromBin(Point*& Tree) { Bin q;

Распечатка бинарного дерева поиска - C++
Много где висит функция void print(int deep, ptree p) { if(p) { print(deep + 1, p->l); for ( int i = 0; i < deep; i ++...

Реализация бинарного дерева поиска - C++
Задача: Реализация бинарного дерева поиска Компилируется нормально, а при запуске выбивает ошибку : "Необработанное исключение по адресу...

Реализация бинарного дерева поиска - C++
Не выводит значения узлов деревьев, как я понял происходит утечка памяти, но я не пойму, что нужно сделать. Программа ошибку не выдаёт....

Итератор дерева бинарного поиска - C++
Если у нас в качестве коллекции выступают вектора, очереди, стеки и т.п. то там вроде бы всё понятно инкремент, декремент итератора...

Итератор для бинарного дерева поиска. - C++
Господа, нужен совет знатоков. Бинарное дерево поиска представлено следующей структурой. template <typename ValueType> struct Node {...

16
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.04.2013, 17:30 #2
Могу дать только свою реализацию структуры бинарного дерева поиска. Ввод информации сама сможешь реализовать?
Файл cmap.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
#ifndef CMAP_H
#define CMAP_H
 
/*
   Модуль структуры вида "словарь" на языке Си.
   Для использования данного модуля НЕОБХОДИМО в файле определения(cmap.c)
   ОБЯЗАТЕЛЬНО задать функцию, сравнивающую ключи и значение(инициализировать
   указатели keyCompareFunc и valueComapareFunc).
   При этом пользовательская функция должна возвращать отрицательное значение,
   если первый аргумент меньше второго, положительное значение, если первый аргумент
   больше второго и должна возвращать 0 в случае равенства двух аргументов
 */
 
#include <stdio.h>
 
struct Map; // опережающее объявление
 
typedef int TKey;   // тип ключа
typedef const char * TValue; // тип значения
 
typedef int (*keyCompareFuncPointer)(TKey, TKey); // указатель на функцию сравнения ключей
//typedef int (*valueComapareFuncPointer) (TValue, TValue); // // указатель на функцию сравнения значения
typedef void (*outNodeFuncPointer) (struct Map *);
 
struct Map
{
   TKey key;
   TValue value;
};
 
struct Node
{
   struct Map map;
   struct Node *left;  // левое поддерево (для меньших значений)
   struct Node *right; // правое поддерево (для бОльших значений)
};
 
/* cmap_has_key() проверяет имеется ли в словаре ключ key
   в случае отсутствия такового возвращает NULL,
   иначе структуру Map, содержащий искомый ключ */
struct Map * cmap_has_key(struct Node *rootNode, TKey key);
TValue cmap_get_value(TKey key);                 // возвращает значение по ключу
/* cmap_insert() вставляет в словарь новую запись.
   В случае, если ключ key уже имеется в словаре, то просто обновляется его value */
int cmap_insert(struct Node **rootNode, TKey key, TValue value);
int cmap_clear(struct Node ** const rootNode);            // очищает словарь
int cmap_empty(const struct Node * const rootNode);             // проверяет на пустоту словарь
/* удаляет элемент словаря по ключу. Возвращает 0 в случае успеха, или
   CMAP_KEY_NOT_FOUND в случае неудачи */
int cmap_delete(struct Node ** const rootNode, TKey key);
void cmap_out(struct Node *rootNode, outNodeFuncPointer outFunc);
 
enum CMAP_ERROR{
   CMAP_NULL_POINTER = 1, // если передан неверный указатель
   CMAP_KEY_NOT_FOUND,     // указанный ключ не найден
   CMAP_MEMORY_ALLOCATE_ERROR // ошибка выделения памяти
};
 
#endif // CMAP_H
Файл cmap.c
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
#include "cmap.h"
 
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
int cmpInt(int a, int b)
{
   return a - b;
}
 
static
keyCompareFuncPointer keyCompareFunc = &cmpInt;
 
/*
static
valueComapareFuncPointer valueComapareFunc = &strcmp;
*/
 
// ------------------------------------------------------------
int cmap_insert(struct Node **rootNode, TKey key, TValue value)
{
   /* cmap_insert() вставляет в словарь новую запись.
   В случае, если ключ key уже имеется в словаре, то просто обновляется его value */
   if (!rootNode)
      return CMAP_NULL_POINTER;
 
   if (*rootNode == 0)
   {
      struct Node *newNode = malloc(sizeof (*newNode));
 
      newNode->map.key = key;
      newNode->map.value = value;
      newNode->left = NULL;
      newNode->right = NULL;
      // пустое дерево, новый элемент есть новый корень
      *rootNode = newNode;
   }
   else
   {
      struct Node *curNode = *rootNode; // текущий узел
      int iCmp; // хранит значение функции сравнения ключа текущего узла и ключа вставки
 
      while (1)
      {
         iCmp = keyCompareFunc(curNode->map.key, key);
 
         if (iCmp < 0)
         {
            // ключ вставки меньше ключа текущего узла
            if (curNode->left != NULL)
               curNode = curNode->left;
            else
            {
               struct Node *newNode = malloc(sizeof (*newNode));
 
               if (!newNode)
                  return CMAP_MEMORY_ALLOCATE_ERROR;
 
               newNode->map.key = key;
               newNode->map.value = value;
               newNode->left = NULL;
               newNode->right = NULL;
 
               curNode->left = newNode;
               break;
            }
         }
         else if (iCmp > 0)
         {
            // ключ вставки больше ключа текущего узла
            if (curNode->right != NULL)
               curNode = curNode->right;
            else
            {
               struct Node *newNode = malloc(sizeof (*newNode));
 
               if (!newNode)
                  return CMAP_MEMORY_ALLOCATE_ERROR;
 
               newNode->map.key = key;
               newNode->map.value = value;
               newNode->left = NULL;
               newNode->right = NULL;
 
               curNode->right = newNode;
               break;
            }
         }
         else
         {
            // ключ вставки равен ключу текущего узла. В таком случае просто обновляем значение узла
            curNode->map.value = value;
            break;
         }
      }
   }
 
   return 0;
}
// ------------------------------------------------------------
struct Map * cmap_has_key(struct Node *rootNode, TKey key)
{
   /* cmap_has_key() проверяет имеется ли в словаре ключ key
   в случае отсутствия такового возвращает NULL,
   иначе структуру Map, содержащий искомый ключ */
 
   if (!rootNode) // если словарь пуст, то мы ничего не нашли
      return NULL;
 
   struct Node *curNode = rootNode; // текущий узел
   int iCmp; // хранит результат сравнения ключа текущего узла и искомого
 
 
   while (1)
   {
      iCmp = keyCompareFunc(curNode->map.key, key);
 
      if (iCmp < 0)
      {
         if (curNode->left == NULL)
            return NULL; // ключ не найден
         else
            curNode = curNode->left;
      }
      else if (iCmp > 0)
      {
         if (curNode->right == NULL)
            return NULL; // ключ не найден
         else
            curNode = curNode->right;
      }
      else
      {
         // если мы здесь, то ключ найден
         return &curNode->map;
      }
   }
}
// ------------------------------------------------------------
int cmap_delete(struct Node ** const rootNode, TKey key)
{
   if (!(*rootNode))
      return CMAP_KEY_NOT_FOUND;
 
   struct Node *parentNode = NULL;
   struct Node *curNode = *rootNode;
   int iCmp;
 
   while (1)
   {
      iCmp = keyCompareFunc(curNode->map.key, key);
 
      if (iCmp < 0)
      {
         if (curNode->left == NULL)
            return CMAP_KEY_NOT_FOUND; // ключ не найден
         else
         {
            parentNode = curNode;
            curNode = curNode->left;
         }
      }
      else if (iCmp > 0)
      {
         if (curNode->right == NULL)
            return CMAP_KEY_NOT_FOUND; // ключ не найден
         else
         {
            parentNode = curNode;
            curNode = curNode->right;
         }
      }
      else
      {
         // если мы здесь, то ключ найден. Выходим из цикла
         break;
      }
   } // end while (1)
 
   if (!curNode->left && !curNode->right) // удаляем узел без потомков
   {
      if (!parentNode) // удаляем весь словарь
         *rootNode = NULL;
      else
      {
         if (parentNode->left == curNode)
            parentNode->left = NULL;
         else
            parentNode->right = NULL;
      }
 
      free(curNode);
   }
   else if (curNode->left && curNode->right) // если удаляемый узел содежит два потомка
   {
      struct Node *leaf = curNode->left; // для нахождения листка
      struct Node *leafParent = curNode;
      // цикл поиска листка у дерева удаляемого элемента
      while (leaf->left || leaf->right) // пока у текущего узла есть дети
      {
         leafParent = leaf;
 
         if (leaf->left)
            leaf = leaf->left;
         else
            leaf = leaf->right;
      }
 
      if (leafParent->left == leaf) // удаляем информацию о листочке у его родителя
         leafParent->left = NULL;
      else
         leafParent->right = NULL;
 
      leaf->left = curNode->left;
      leaf->right = curNode->right;
 
      if (parentNode) // если удаляем не самый корень дерева
      {
         // заменяем удаляемый элемент листком из его поддерева
         if (parentNode->left == curNode)
            parentNode->left = leaf;
         else
            parentNode->right = leaf;
      }
      else // усли удаляем самый корень дерева
      {
         *rootNode = leaf;
      }
 
      free(curNode);
   }
   else // если у удаляемого узла только один потомок
   {
      if (parentNode)
      {
         if (parentNode->left == curNode)
            parentNode->left = curNode->left ? curNode->left : curNode->right;
         else
            parentNode->right = curNode->left ? curNode->left : curNode->right;
      }
      else // удаляем самый корень дерева
      {
         *rootNode = parentNode->left = curNode->left ? curNode->left : curNode->right;
      }
 
      free(curNode);
   }
 
   return 0;
}
// ------------------------------------------------------------
int cmap_empty(const struct Node * const rootNode)
{
   return rootNode == NULL;
}
// ------------------------------------------------------------
int cmap_clear(struct Node ** const rootNode)
{
   /* Функция очистки диски. УЖАСНЕЙШАЯ реализация, как будет время надо переделать!!!!!
    */
 
   if (!rootNode)
      return CMAP_NULL_POINTER;
   while (!cmap_empty(*rootNode))
      cmap_delete(rootNode, (**rootNode).map.key);
 
   return 0;
}
// -----------------------------------------------------------
void cmap_out(struct Node *rootNode, outNodeFuncPointer outFunc)
{
   // ужаснейщая реализация. Необходимо задействовать структуру типа стэка
   // вместо рекурсии
   if (!rootNode)
      return;
 
   if (rootNode->left)
      cmap_out(rootNode->left, outFunc);
 
   outFunc(&rootNode->map);
   printf("\n");
 
   if (rootNode->right)
      cmap_out(rootNode->right, outFunc);
}
// -----------------------------------------------------------
0
Anastasiya1
0 / 0 / 0
Регистрация: 21.03.2013
Сообщений: 77
16.04.2013, 17:34  [ТС] #3
Вообще не понимаю......
0
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.04.2013, 17:41 #4
Anastasiya1, а что за файл? Можете показать примерное его содержание? А то я сам не понимаю, зачем здесь бинарное дерево поиска?
0
Anastasiya1
0 / 0 / 0
Регистрация: 21.03.2013
Сообщений: 77
16.04.2013, 17:48  [ТС] #5
Просто текстовый файл(в нем содержится алфавит), ну так вот считывая из этого файла нужно создать дерево

Добавлено через 1 минуту
Тоесть каждый потомок дерева должен содержать один элемент, тоесть одну букву.

Добавлено через 14 секунд
Тоесть каждый потомок дерева должен содержать один элемент, тоесть одну букву.
0
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.04.2013, 17:48 #6
Anastasiya1, бинарное дерево поиска содержит как минимум два компонента - ключ и значение. А то, что вы написали выше скорее похоже на множество. Можете все-таки привести пример входного файла???
0
Anastasiya1
0 / 0 / 0
Регистрация: 21.03.2013
Сообщений: 77
16.04.2013, 17:59  [ТС] #7
Я незнаю как вам иначе объяснить(
Значением и будет являтся буква.
0
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.04.2013, 18:11 #8
Смысла в этом я не вижу никакого. Может, там русско-английский словарь или что-то вроде этого?
0
Anastasiya1
0 / 0 / 0
Регистрация: 21.03.2013
Сообщений: 77
16.04.2013, 18:24  [ТС] #9
Нет, просто от балды создать дерево( и все...Это просто, просто я отсутствовала и не совсем понимаю эту тему(

Добавлено через 11 минут
Получается, как обход дерева в ширину.Корень не имеет значения, левый потомок имеет значение "a", правый "b" и так до "z".Все эти элементы(буквы) считываются с файла...И все Вы мне можете хоть как то помочь?
0
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.04.2013, 19:48 #10
Что должно уметь это бинарное дерево?? Определять, есть ли слово в текстовом файле?
0
Anastasiya1
0 / 0 / 0
Регистрация: 21.03.2013
Сообщений: 77
16.04.2013, 19:57  [ТС] #11
Да нет же, как я поняла просто считать из текстового файла алфавит создав дерево
0
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.04.2013, 20:42 #12
То, что вы говорите - ерунда полнейшая! Повторяю в сотый раз. Что должно уметь это ваше "бинарное дерево поиска"? Из каких компонентов должен состоять узел дерева?
0
Anastasiya1
0 / 0 / 0
Регистрация: 21.03.2013
Сообщений: 77
16.04.2013, 20:46  [ТС] #13
"-" и ".", как в азбуке морза
0
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
16.04.2013, 20:54 #14
Т.е. Напротив каждой буквы стоит ее эквивалент в азбуке Морзе?
0
Anastasiya1
0 / 0 / 0
Регистрация: 21.03.2013
Сообщений: 77
16.04.2013, 21:02  [ТС] #15
Ну что-то в этом роде.Тут файлы можно прикреплять?
0
16.04.2013, 21:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.04.2013, 21:02
Привет! Вот еще темы с ответами:

Удаления узла из бинарного дерева поиска - C++
Уже довольно много времени убил на эту задачу, теорию понимаю, на практике реализовать никак не получается. Помогите пожалуйста написать...

Вычисление высоты бинарного дерева поиска на С++ - C++
Никак не могу вывести нормально высоту дерева, уже второй день маюсь, подскажите пожалуйста, в чем проблема ? Например : Высоту...

(ищу) Алгоритм построения бинарного дерева поиска - C++
Помогите пожалуйста. Если у кого завалялся алгоритм построения бинарного дерева поиска. Поделитесь. Очень нужно. Желательно что-бы цифры...

Мистика при удалении из бинарного дерева поиска ! - C++
Привет народ !) Пытаюсь создать функцию удаления листа из бинарного дерева поиска : template&lt;typename NODETYPE&gt; void...


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

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

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