Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17

Поиск по бинарному дереву целочисленных значений

05.12.2012, 18:43. Показов 2927. Ответов 23
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте! Очень нужна помощь данном, надеюсь что простом, задании. Заранее спасибо!

Реализовать поиск по бинарному дереву целочисленных значений, генерируемых случайным образом. Кол-во чисел и диапазон задаётся пользователем. Этапы решения:
1) Построить бинарное дерево по созданному случайным образом массиве.
2) Реализовать алгоритм поиска значения, введённого пользователем с выч. сложностью O(nlog(n)) т.е. ответить на вопрос "содержится ли такое значение в дереве".
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
05.12.2012, 18:43
Ответы с готовыми решениями:

Итератор по бинарному дереву
Всем привет! Помогите пожалуйста! Пишу бинарное дерево, нужно реализовать итератор по нему. Не очень понимаю, как это грамотно сделать( ...

Подключение к бинарному дереву списка
Вот есть такой вот код. Не могу подключить к моему узлу бинарного дерева односвязный список Кто-то может помочь? //...

Итератор для обхода по бинарному дереву
Кхм. Попытался реализовать итератор для обхода по бинарному дереву... Наткнулся на запару. Дерево должно быть обязательно круговым, чтобы...

23
 Аватар для Wolkodav
842 / 480 / 58
Регистрация: 18.09.2012
Сообщений: 1,688
05.12.2012, 18:45
Что конкретно вы не понимаете?
0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 18:48  [ТС]
Цитата Сообщение от Wolkodav Посмотреть сообщение
Что конкретно вы не понимаете?
Честно говоря, вообще ничерта не смыслю, начиная с того что такое бинарное дерево.
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.12.2012, 18:52
smeaz, под свои нужды подстроишь. Сразу говорю, что там память вроде как не освобождается.
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
#include <iostream>
#include <conio.h>
#include <fstream>
using namespace std;
 
struct  bin_tree
{
   int value;
   bin_tree *left, *right;
}*pHead = NULL; // указатель на вершину равен нулю
 
// добавление конкретного узла дерева
void add_node(bin_tree*, int); 
// проверка на "пустоту" дерева, если указатель на вершину равен нулю, создает узел
void add_bin_tree(int);
// обход
void print(bin_tree*);
void traversal(bin_tree*, ofstream&);
int h_tree(bin_tree *);
 
int main()
{
    setlocale (LC_ALL, "Russian");
    int choose, el;
    cout<< "1. Загрузить последовательность с файла\n"
        << "2. Ввести последовательность вручную\n\n"
        << "Ваш выбор: ";
    do{ cin>> choose;} while(choose != 1 && choose != 2);
    if (choose == 1)
    {        
        ifstream iz("bin.txt");
        if (iz.bad()) return 1;
        while(!iz.eof() && iz>> el)
            add_bin_tree (el);     
        iz.close();
    }
    
    if (choose == 2)
    {
        cout<< "Информационные поля вершин дерева:\n";
        while(cin>> el)
            add_bin_tree (el);
    }
    ofstream o("bin.txt");
    print (pHead);
    traversal (pHead, o);
    getch();
    o.close();
    return 0;
}
 
void add_node(bin_tree* tree, int value) // добавление конкретного узла дерева
{
    if(value < tree->value)
    { 
        if(tree->left != NULL) // если значение меньше, двигаемся по "левой ветке"
            add_node(tree->left, value);
        else
        {  
            tree->left = new bin_tree;
            tree->left->value = value;
            tree->left->left = NULL;
            tree->left->right = NULL;
        }
    }
 
    if(value > tree->value) // иначе двигаемся по правой 
    { 
        if(tree->right != NULL)
            add_node(tree->right, value);
        else
        {
            tree->right = new bin_tree;
            tree->right->value = value;
            tree->right->left=NULL;
            tree->right->right=NULL;
        }
    }
 
    if(value == tree->value)                
        cout<< value<< " is already in tree"<< endl;
}
 
void add_bin_tree(int value)
{
    if(pHead == NULL) // если дерево пустое - создадим первый узел
    {
       pHead = new bin_tree;
       pHead->value = value;
       pHead->left = NULL;
       pHead->right = NULL;
    }
    else
        add_node(pHead, value); // если в вершине уже что-то есть - добавляем слева или справа 
}
 
void traversal(bin_tree* tree, ofstream &o)
{     
    if (tree != NULL)
    { 
        traversal(tree->left, o);
        o<< tree->value<< " ";
        traversal(tree->right, o);
    }
}
 
void print(bin_tree* tree)
{     
    if (tree != NULL)
    { 
        print(tree->left);
        cout<< tree->value<< " ";
        print(tree->right);
    }
}
 
int h_tree(bin_tree* tree)
{
     int h = 1, m = 0, s;
     if (tree == NULL)
        return 0;
     s = h_tree(tree->left);
     if (s > m)
         m = s;
     s = h_tree(tree->right);
     if (s > m)
         m = s;
     return h + m;
}
Чтобы понять бинарное дерево -
ручка и листок бумаги
1
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 18:55  [ТС]
Цитата Сообщение от MrGluck Посмотреть сообщение
под свои нужды подстроишь.
Боюсь что я смогу только испортить код..
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.12.2012, 19:00
Цитата Сообщение от smeaz Посмотреть сообщение
Боюсь что я смогу только испортить код..
Ты СЧ генерировал хоть раз?
C++
1
2
while(cin>> el)
            add_bin_tree (el);
меняешь первую строчку на el = СЧ
ГСЧ (ГПСЧ) сам создашь, такие основы вполне сам домыслить.

далее, смотри внимательно на ф-цию add_node
А конкретно на строчки:
C++
1
2
if(value == tree->value)                
        cout<< value<< " is already in tree"<< endl;
Берешь и удаляешь все, где идет добавление элемента, оставляешь лишь переходы Т.е. if (value < tree->value) {переход} и if (value > tree->value) {переход }
0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 19:10  [ТС]
Цитата Сообщение от MrGluck Посмотреть сообщение
Ты СЧ генерировал хоть раз?
Я впервые сталкиваюсь с языком программирования вообще.
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.12.2012, 19:16
Цитата Сообщение от smeaz Посмотреть сообщение
Я впервые сталкиваюсь с языком программирования вообще.
А до этого вы что делали? Бинарные деревья предполагают рекурсию, структуры, функции. Это дают точно не сразу.

для СЧ:
C++
1
2
3
4
5
6
7
#include <cstdlib>
#include <ctime>
 
 
srand (time(0));
cin >> a >> b; // наш диапазон
cout<<  a + rand() % (b-a + 1); // наше СЧ
0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 19:23  [ТС]
Цитата Сообщение от MrGluck Посмотреть сообщение
А до этого вы что делали?
Списывал По правде говоря начинаю припоминать, было какое-то программирование у нас конечно, но то был не С++ и я понятия не имею куда эту генерацию случайных чисел вставлять.. Вы уж меня извините Мне бы просто задание сделать и забыть это как страшный сон, да простят меня местные форумчане..
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.12.2012, 19:27
smeaz, я же вам прям тыкнул пальцем:
Поиск по бинарному дереву целочисленных значений
C++
1
2
3
4
5
6
7
8
9
10
11
if (choose == 2)
{
    cout<< "Введите диапазон [a, b]: "
    int a, b, N;
    cin >> a >> b;
    cout<< "Введите количество чисел: "
    cin >> N;
    srand (time (0));
    for (int i=0; i < N; i++)
        add_bin_tree (a + rand() % (b - a + 1));
}
0
Заблокирован
05.12.2012, 19:32
Цитата Сообщение от smeaz Посмотреть сообщение
сложностью 0(nlog(n))
хм.. если бинарное дерево построено, то это какая-то странная асимптотика
0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 19:52  [ТС]
Цитата Сообщение от adm_loro Посмотреть сообщение
хм.. если бинарное дерево построено, то это какая-то странная асимптотика
Думаю я неправильно разобрал почерк в тексте задания.. Тут же, просто картинкой нельзя почему-то выложить... Возможно это не ноль, а буква O, я вообще без понятия..

Добавлено через 1 минуту
Цитата Сообщение от MrGluck Посмотреть сообщение
smeaz, я же вам прям тыкнул пальцем:
Да хоть носом в монитор, говорю же, нихрена не понимаю я в этом деле.. Операции сложнее копипаста мне не по силам...

Добавлено через 13 минут
Попробую выложить фотку ещё раз для уточнения этой детали, надеюсь на адекватность и человечность модератора.
 Комментарий модератора 
Правила есть правила (п. 5.18 правил форума). Вам сложно перепечатать задание?
0
Заблокирован
05.12.2012, 19:55
да это O, а не ноль но вот поиск по дереву в худшем случая линеен, если дерево не сбалансировано, а так O(H), где Н-высота дерева. Вообщем не парься - иди в армию.
0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 19:57  [ТС]
Цитата Сообщение от adm_loro Посмотреть сообщение
Вообщем не парься - иди в армию.
Спасибо за совет, но я три курса уже "отучился", так что это не вариант))
0
05.12.2012, 19:58

Не по теме:

Цитата Сообщение от MrGluck Посмотреть сообщение
C++
1
for (int i=0; i < N; i++) add_bin_tree (a + rand() % (b - a + 1));
Так же не будет поиска за О(log(n)), дерево же небалансируемое, или я что-то упустил?

0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 20:00  [ТС]
Цитата Сообщение от BumerangSP
Вам сложно перепечатать задание?
Как видите да, возникли сложности..
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
05.12.2012, 20:02
Цитата Сообщение от gray_fox Посмотреть сообщение

Не по теме:


Так же не будет поиска за О(log(n)), дерево же небалансируемое, или я что-то упустил?

Я лишь показал как рандомными значениями заполнить. Т.е.
1) Построить бинарное дерево по созданному случайным образом массиве.
На массив легко переписать.

А если с балансировкой - то это либо АВЛ деревья, либо КЧ деревья, но я даже боюсь выкладывать свою лабу с ними, т.к. синтаксис надо вкуривать конкретно) А чтоб понять суть нужно вечерок посидеть попотеть. Но ТС даже не может СЧ получить, о чем речь тогда.
0
05.12.2012, 20:06

Не по теме:

MrGluck, ну зачем дерево с балансировкой. Думаю из массива можно сразу построить сбалансированное дерево. Это, конечно, уже не совсем в тему)

0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 20:23  [ТС]
BumerangSP Не могу найти как ответить на ЛС.. Слишком быстро трёте сообщения, я же написал, нужно исправить ноль на букву O.
0
05.12.2012, 20:25

Не по теме:

smeaz, где log? Исправлено.

1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
05.12.2012, 20:25
Помогаю со студенческими работами здесь

Довести до ума программу про бинарному дереву
Здравствуйте. Помогите пожалуйста привести до ума задачу: организовать бинарное дерево по заданной последовательности и функцию включения...

Поиск по бинарному дереву, построение бинарного дерева
Сделал 3 процедуры: 1. строит бинарное дерево 2. рекурсивная процедура помогает 1-ой найти необходимую позицию (она то и неправильно...

Как осуществить поиск по дереву значений?
В общем есть внешняя обработка с деревом значений с тремя столбиками (Должность,ФИО,Зарплата).Все работает как-то так: Процедура...

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

Поиск по дереву
По задании надо сделать поиск по дереву и найти минимальный возраст.


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru