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

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

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

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

Реализовать поиск по бинарному дереву целочисленных значений, генерируемых случайным образом. Кол-во чисел и диапазон задаётся пользователем. Этапы решения:
1) Построить бинарное дерево по созданному случайным образом массиве.
2) Реализовать алгоритм поиска значения, введённого пользователем с выч. сложностью O(nlog(n)) т.е. ответить на вопрос "содержится ли такое значение в дереве".
0

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

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.12.2012, 18:43
Ответы с готовыми решениями:

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

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

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

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

23
620 / 474 / 58
Регистрация: 18.09.2012
Сообщений: 1,688
05.12.2012, 18:45 2
Что конкретно вы не понимаете?
0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 18:48  [ТС] 3
Цитата Сообщение от Wolkodav Посмотреть сообщение
Что конкретно вы не понимаете?
Честно говоря, вообще ничерта не смыслю, начиная с того что такое бинарное дерево.
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
05.12.2012, 18:52 4
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  [ТС] 5
Цитата Сообщение от MrGluck Посмотреть сообщение
под свои нужды подстроишь.
Боюсь что я смогу только испортить код..
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
05.12.2012, 19:00 6
Цитата Сообщение от 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  [ТС] 7
Цитата Сообщение от MrGluck Посмотреть сообщение
Ты СЧ генерировал хоть раз?
Я впервые сталкиваюсь с языком программирования вообще.
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
05.12.2012, 19:16 8
Цитата Сообщение от 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  [ТС] 9
Цитата Сообщение от MrGluck Посмотреть сообщение
А до этого вы что делали?
Списывал По правде говоря начинаю припоминать, было какое-то программирование у нас конечно, но то был не С++ и я понятия не имею куда эту генерацию случайных чисел вставлять.. Вы уж меня извините Мне бы просто задание сделать и забыть это как страшный сон, да простят меня местные форумчане..
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
05.12.2012, 19:27 10
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 11
Цитата Сообщение от smeaz Посмотреть сообщение
сложностью 0(nlog(n))
хм.. если бинарное дерево построено, то это какая-то странная асимптотика
0
0 / 0 / 0
Регистрация: 05.12.2012
Сообщений: 17
05.12.2012, 19:52  [ТС] 12
Цитата Сообщение от adm_loro Посмотреть сообщение
хм.. если бинарное дерево построено, то это какая-то странная асимптотика
Думаю я неправильно разобрал почерк в тексте задания.. Тут же, просто картинкой нельзя почему-то выложить... Возможно это не ноль, а буква O, я вообще без понятия..

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

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

Не по теме:

Цитата Сообщение от 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  [ТС] 16
Цитата Сообщение от BumerangSP
Вам сложно перепечатать задание?
Как видите да, возникли сложности..
0
Форумчанин
Эксперт CЭксперт С++
8165 / 5013 / 1436
Регистрация: 29.11.2010
Сообщений: 13,455
05.12.2012, 20:02 17
Цитата Сообщение от gray_fox Посмотреть сообщение

Не по теме:


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

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

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

Не по теме:

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

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

Не по теме:

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

1
05.12.2012, 20:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2012, 20:25
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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