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

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

Войти
Регистрация
Восстановить пароль
 
eisenheim
18 / 8 / 1
Регистрация: 06.06.2011
Сообщений: 268
#1

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

15.01.2013, 23:11. Просмотров 533. Ответов 5
Метки нет (Все метки)

Помогите реализовать дерево двоичного поиска (операции добавления данных, прямого обхода с печатью ключей).
Буду ооооочень благодарен

Добавлено через 3 часа 29 минут
Апп
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.01.2013, 23:11     Дерево двоичного поиска
Посмотрите здесь:

Бинарный поиск (Сложность двоичного поиска) - C++
Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино...

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

Написать функцию двоичного поиска в упорядоченном по алфавиту массиве слов - C++
Написать функцию двоичного поиска в упорядоченном по алфавиту массиве слов

Частотный словарь из слов текстового файла в виде дерева двоичного поиска - C++
Задача: Построить частотный словарь из слов текстового файла в виде дерева двоичного поиска. Вывести его на экран в виде дерева....

Ввести число и найти в массиве ближайшее к нему методом двоичного поиска - C++
Ввести массив целых чисел и отсортировать его ( можно использовать qsort).Ввести число и найти в массиве ближайшее к нему методом двоичного...

Посредством двоичного поиска найти такой минимальный элемент, чтобы выполнялось заданное условие - C++
Даны массивы min и max, отсортированные по невозрастанию и число k. С помощью двоичного поиска найти такой элемент минимальный i, чтобы...

Дан типизированный файл с данными о росте. Используя метод двоичного поиска вывести фамилию по росту - C++
С++ дан типизированный файл с данными о росте 25 учеников.Используя метод двоичного поиска вывести фамилию по заданному росту.Помогите...

Дерево поиска - C++
Всем добрый полдень:) Помогите пож-та решить вот такую вот задачку: В текстовом файле задан алфавит(на англ(a-z), нужно построить...

дерево поиска - C++
Помогите написать прог-му на С++ задача: Написать программу построения частотного словаря слов некоторого текста в виде дерева...

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

Дерево бинарного поиска - C++
Всем привет! Есть рабочий код бинарного поиска template <class Item, class Key> class ST { private: struct node { Item item;...

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


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Invader_Zim
Twilight Parasite
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 907
15.01.2013, 23:14     Дерево двоичного поиска #2
std::map чем плох? Реализован-то как дерево. Посмотри сырец)
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
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
16.01.2013, 01:27     Дерево двоичного поиска #4
поищи на форуме. тут эти темы одни и те же периодически создаются
MrGluck
Модератор
Эксперт CЭксперт С++
7147 / 4313 / 629
Регистрация: 29.11.2010
Сообщений: 11,730
16.01.2013, 01:41     Дерево двоичного поиска #5
Invader_Zim, std::map - отсортированный ассоциативный контейнер, использующий К/Ч деревья для балансировки. Бинарное дерево - структура данных, содержащая указатели на саму себя так, что левая подветвь имеет значение меньше текущей, правая больше. Совсем другое.
Kuzia domovenok прав, тем пруд пруди, автор слишком ленив и хочет, чтобы ему прям под нос все сунули, а потом сдать чужой код, даже не понимая, как оно работает.
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     Дерево двоичного поиска
Ответ Создать тему
Опции темы

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