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

Дерево двоичного поиска - C++

Восстановить пароль Регистрация
 
eisenheim
 Аватар для eisenheim
18 / 8 / 1
Регистрация: 06.06.2011
Сообщений: 268
15.01.2013, 23:11     Дерево двоичного поиска #1
Помогите реализовать дерево двоичного поиска (операции добавления данных, прямого обхода с печатью ключей).
Буду ооооочень благодарен

Добавлено через 3 часа 29 минут
Апп
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Invader_Zim
Twilight Parasite
 Аватар для Invader_Zim
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 907
15.01.2013, 23:14     Дерево двоичного поиска #2
std::map чем плох? Реализован-то как дерево. Посмотри сырец)
eisenheim
 Аватар для eisenheim
18 / 8 / 1
Регистрация: 06.06.2011
Сообщений: 268
16.01.2013, 01:22  [ТС]     Дерево двоичного поиска #3
Цитата Сообщение от Invader_Zim Посмотреть сообщение
std::map чем плох? Реализован-то как дерево. Посмотри сырец)
1) Извини, но что это?
2) Мне надо преподу сдать программу. Знаю, что начать нужно как-то в этом роде:

C++
1
2
3
4
5
struct Tree {
// int num; - не уверен, что это нужно
Tree *left;
Tree *right;
}
Помогите пожалуйста
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
16.01.2013, 01:27     Дерево двоичного поиска #4
поищи на форуме. тут эти темы одни и те же периодически создаются
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,404
16.01.2013, 01:41     Дерево двоичного поиска #5
Invader_Zim, std::map - отсортированный ассоциативный контейнер, использующий К/Ч деревья для балансировки. Бинарное дерево - структура данных, содержащая указатели на саму себя так, что левая подветвь имеет значение меньше текущей, правая больше. Совсем другое.
Kuzia domovenok прав, тем пруд пруди, автор слишком ленив и хочет, чтобы ему прям под нос все сунули, а потом сдать чужой код, даже не понимая, как оно работает.
eisenheim
 Аватар для eisenheim
18 / 8 / 1
Регистрация: 06.06.2011
Сообщений: 268
16.01.2013, 02:00  [ТС]     Дерево двоичного поиска #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
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
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
 
//структура для хранения узла дерева
struct Node
{
 int  key;  //ключ
 Node *parent; //ссылка на родителя, для root = 0
 Node *left;  //ссылка на левого потомка
 Node *right;  //ссылка на пр
 авого потомка
 Node *head;  //начало кольца одинаковых ключей
 Node *tail;  //конец  кольца одинаковых ключей
 char *str;  //адрес строки
};
 
//структура для отображения дерева
struct OutTree
{
 Node *node;  //узел
 int  level;  //уровень узла, 0 (корень), 1, 2,... 
 int  offset;  //индексы поля, 0 для 0, 0,1 для 1, 0-3 для 2 и т.д.
};
 
Node *root = NULL; //корень дерева
 
Node * CreateNode(int iKey, char * sInfo)
{
 Node * node;
 
 //создаем новый узел (calloc очищает выделяемую память)
 node = (Node*)calloc(1, sizeof(Node));
 //заполняем поля
 node->key = iKey;    //ключ
 node->str = (char*)malloc(strlen(sInfo)+1);
 strcpy(node->str, sInfo);  //инфо
 return node;
}
 
//вставка узла с указанным ключом и данными
void NodeInsert(int iKey, 
 char * sInfo)
{
 Node *nodeParent = NULL;  //родитель текущего узла
 Node *node = root;   //некущий узел
 Node *nodeNew;    //
новый узел
  
 // Пока ещё есть узлы, которые надо просмотреть, 
 // то есть пока мы не добрались до “листочков” дерева
 while (node)
 {
  nodeParent = node;   //текущий узел для потомков является родителем
  // Выбираем узел, в зависимости от того,
  // меньше или больше вставляемый ключ относительно текущего узла
  if (iKey < node->key)
   node = node->left;
  else if (iKey > node->key)
   node = node->right;
  //если равно, то добавляем в конец кольца
  else
  {
   nodeNew
= CreateNode(iKey, sInfo); //создаем новый узел
   if (node->tail)      //кольцо уже есть?
   {
    nodeNew->tail = node->tail;  //вставляем в конец цепочки кольца
    nodeNew->head = node;   //правим ссылки
    node->tail->head = nodeNew;
    node->tail = nodeNew;
   }
   else        //не было - добавляем первое в кольцо
   {
    node->tail = node->head = nodeNew;
    nodeNew->
 ;head = nodeNew->tail = node;
   }
   //выходим
   return;
  }
 }
            //добавляем узел в дерево
 nodeNew = CreateNode(iKey, sInfo);   //создаем
 nodeNew->parent = nodeParent;    //родитель
 
 if (nodeParent == NULL)  //если в дереве ещё нет узлов
  root = nodeNew;   //то запомним, как корень
 else
 {
  // Если ключ узла, который мы хотим вставить, 
  // меньше ключа узла, потомком которого должна стать 
  // вставляемый узел
  if (iKey < nodeParent->key)
   nodeParent->left
= nodeNew; //то добавить в дерево как левого потомка
  else
   nodeParent->right = nodeNew;//иИначе добавить в дерево как правого потомка
 }
}
 
//----------------------------------------
//подпрограммы, вызываемые из меню
//----------------------------------------
 
//добавление узла 
void AddKey(void)
{
 int  iKey;
 char sInfo[256];
 
 //запросим ключ
 printf("\nEnter key: ");
 scanf("%d", &iKey);
 //и Info
 printf("Enter
info: ");
 do
 {
  gets(sInfo);
 }while(0==sInfo[0]);   //строка должна быть непустой!
 
 NodeInsert(iKey, sInfo);  //заносим в дерево
 printf("Node added");
}

Не могли бы вы помочь оставить нужное и отредактировать, как надо?
Yandex
Объявления
16.01.2013, 02:00     Дерево двоичного поиска
Ответ Создать тему
Опции темы

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