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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
nidaime
3 / 3 / 0
Регистрация: 28.11.2011
Сообщений: 35
#1

Бинарное дерево, стандартная библиотека шаблонов (STL) - C++

16.11.2013, 20:22. Просмотров 1885. Ответов 8
Метки нет (Все метки)

Моя задача заключается в следующем:
Построить шаблон класса "бинарное дерево" со следующими возможностями:
1) возможность добавления и удаления определенного элемента (по значению ключа)
2) поиск (по ключу)

Нужно использовать стандартный контейнерный класс. И как раз тут мне нужна помощь ( с контейнерными классами впервые столкнулся) - скажите пожалуйста какие стандартные контейнерные классы помогут в работе с бинарными деревьями и как именно. Спасибо
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2013, 20:22     Бинарное дерево, стандартная библиотека шаблонов (STL)
Посмотрите здесь:

стандартная библиотека C++
C++ Стандартная библиотека шаблонов (STL)
C++ Стандартная библиотека шаблонов STL и класс list по работе с двунаправленным списком
Стандартная библиотека шаблонов STL и класс list по работе с двунаправленным списком C++
C++ Стандартная библиотека C++ и STL
STL, или другая библиотека шаблонов C++
STL бинарное дерево C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
17.11.2013, 00:01     Бинарное дерево, стандартная библиотека шаблонов (STL) #2
может, они хотели, чтобы вы <list> использовали... странное задание.
MrCold
852 / 750 / 71
Регистрация: 11.01.2012
Сообщений: 1,942
17.11.2013, 02:28     Бинарное дерево, стандартная библиотека шаблонов (STL) #3
Цитата Сообщение от nidaime Посмотреть сообщение
скажите пожалуйста какие стандартные контейнерные классы помогут в работе с бинарными деревьями и как именно
Можно сделать обход в ширину с помощью очереди
Или не рекурсивный обход с помощью стэка
... Хотя правда странно
nidaime
3 / 3 / 0
Регистрация: 28.11.2011
Сообщений: 35
17.11.2013, 04:29  [ТС]     Бинарное дерево, стандартная библиотека шаблонов (STL) #4
Уточнил задание, сказали что обязательно сделать только первые два пункта, а использовать стандартный контейнерный класс можно (но не обязательно), если он упростит задание. Так вот, нужно ли использовать что-то другое, или проще будет без каких либо стандартных контейнеров ?

Цитата Сообщение от salam Посмотреть сообщение
может, они хотели, чтобы вы <list> использовали... странное задание.
По определению бинарного дерева каждый его элемент содержит собственную информацию и ссылки на левое и правое поддеревья, растущие из этого элемента, а <list> это двусвязный список, и его элемент тоже содержит собственную информацию и ссылки на предыдущий и последующий элементы, может с помощью <list> и будет легче всего реализовать задачу ?

Цитата Сообщение от MrCold Посмотреть сообщение
Можно сделать обход в ширину с помощью очереди
Или не рекурсивный обход с помощью стэка
... Хотя правда странно
Точно не знаю, но почему-то мне кажется что это осложнит задание..
MrGluck
Ворчун
Эксперт CЭксперт С++
6660 / 3851 / 509
Регистрация: 29.11.2010
Сообщений: 10,200
17.11.2013, 04:34     Бинарное дерево, стандартная библиотека шаблонов (STL) #5
Мб имелось ввиду то, что разрабатываемый вами класс должен быть просто шаблонным?
nidaime
3 / 3 / 0
Регистрация: 28.11.2011
Сообщений: 35
17.11.2013, 04:48  [ТС]     Бинарное дерево, стандартная библиотека шаблонов (STL) #6
Цитата Сообщение от MrGluck Посмотреть сообщение
Мб имелось ввиду то, что разрабатываемый вами класс должен быть просто шаблонным?
Да, но при этом можно использовать стандартный контейнерный класс
MrGluck
Ворчун
Эксперт CЭксперт С++
6660 / 3851 / 509
Регистрация: 29.11.2010
Сообщений: 10,200
17.11.2013, 04:53     Бинарное дерево, стандартная библиотека шаблонов (STL) #7
Цитата Сообщение от nidaime Посмотреть сообщение
Да, но при этом можно использовать стандартный контейнерный класс
а зачем?
Ну разве что std::unique_ptr для хранения информации об узлах.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
17.11.2013, 08:04     Бинарное дерево, стандартная библиотека шаблонов (STL) #8
лично я не стал бы никаких стандартных контейнеров использовать. возможно, просто неграмотен.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2013, 10:37     Бинарное дерево, стандартная библиотека шаблонов (STL)
Еще ссылки по теме:

C++ Организация шаблонов на языке С++, библиотека STL
C++ Стандартная библиотека шаблонов
Библиотека шаблонов STL C++
Библиотека стандартных шаблонов STL C++
Бинарное дерево поиска: "Библиотека", поиск по автору книги C++

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

Или воспользуйтесь поиском по форуму:
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
17.11.2013, 10:37     Бинарное дерево, стандартная библиотека шаблонов (STL) #9
Цитата Сообщение от nidaime Посмотреть сообщение
скажите пожалуйста какие стандартные контейнерные классы помогут в работе с бинарными деревьями и как именно
std::map построен на основе дерева, так что можно просто написать класс-обертку для него

или вот очень веселый вариант с заменой адресных операций на индексные с помощью векторов. преимущество такого решения в скорости выполнения, т.к. избавляет от частых операций выделения памяти с помощью new
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
#include <vector>
#include <stack>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
 
typedef int item_t;
typedef int index_t;
 
const int N = 101;                      // максимальное кол-во элементов в дереве = 100 (элемент с индексом 0 будет выполнять роль nullptr)
 
// замена структуры для хранения узлов дерева
std::vector< item_t > item( N, 0 );     // полезные данные в дереве
std::vector< index_t > left( N, 0 );    // индекс левого потомка
std::vector< index_t > right( N, 0 );   // индекс правого потомка
 
std::stack< index_t > fre;              // накопитель свободных узлов. Можно заменить на что-то другое, на очередь например
 
// вектора можно ресайзами увеличивать/уменьшать до нужных размеров, так что от ограничения N можно избавиться
 
index_t root = 0;                       // индекс корня дерева
 
void init() // засовываем в накопитель все свободные узлы, кроме 0 (nullptr)
{
    for ( index_t i = 1; i < N; ++i )
        fre.push( i );
}
 
void insert( index_t &r, item_t x )
{
    if ( !r )
    {
        r = fre.top(); fre.pop();
        item[ r ] = x;
        return;
    }
    if ( x < item[ r ] ) insert( left[ r ], x );
    else insert( right[ r ], x );
}
 
bool search( index_t r, item_t x )
{
    if ( !r ) return false;
    if ( x < item[ r ] ) return search( left[ r ], x );
    if ( x > item[ r ] ) return search( right[ r ], x );
    return true;
}
 
bool remove_leaf( index_t &r, item_t x )
{
    if ( !r ) return false;
    if ( x == item[ r ] && !left[ r ] && !right[ r ] )
    {
        fre.push( r ); r = 0;
        return true;
    }
    if ( x < item[ r ] ) return remove_leaf( left[ r ], x );
    return remove_leaf( right[ r ], x );
}
 
void show( index_t r, int sh )
{
    if ( !r ) return;
    show( right[ r ], sh + 3 );
    std::cout << std::setw( sh ) << item[ r ] << std::endl;
    show( left[ r ], sh + 3 );
}
 
int rand_item()
{
    return std::rand() % 100;
}
 
int main()
{
    int c;
    item_t x;
 
    srand( time( 0 ) );
    init();
    while ( true )
    {
        std::cin >> c;
        switch ( c )
        {
            case 0:
                std::cin >> x;
                insert( root, x );
                break;
            case 1:
                std::cin >> x;
                std::cout << ( search( root, x ) ? "++" : "--" ) << std::endl;
                break;
            case 2:
                std::cin >> x;
                std::cout << ( remove_leaf( root, x ) ? "++" : "--" ) << std::endl;
                break;
            case 3:
                show( root, 3 );
                break;
        }
    }
 
    return 0;
}
остается завернуть это в шаблонный класс. item_t нужно сделать шаблонным параметром. для данного примера реальный тип данных должен поддерживать операции присваивания, сравнения, ввода из потока и вывода в поток.
вроде всё
Yandex
Объявления
17.11.2013, 10:37     Бинарное дерево, стандартная библиотека шаблонов (STL)
Ответ Создать тему
Опции темы

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