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

Алгоритм реализации двоичного дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 5.00
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
06.09.2010, 23:40     Алгоритм реализации двоичного дерева #1
Нужно написать реализацию двоичного дерева с использованием шаблонов в упрощенном виде следуя конвенциям STL контейнеров. Основные операции: вставка, удаление, поиск и итератор.
>> Абстрактного шаблонного двоичного дерева?
Да
>> Вставка, удаление, поиск, итератор соответственно писать самому, не используя STL
Да

То есть. Суть в том, чтобы написать это все без использования STL, но чтобы оно было похоже на STL. Фактически написать новый контейнер и определить для него операции.
Естественно, я не прошу кода. Прошу только натолкнуть на мысль, как возможно сие реализовать. Заранее спасибо.

Добавлено через 25 минут
По сути я представляю это как-то так... Верно или нет?

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
template<class T>
class BinTree
{
public:
   BinTree():parent(0), left(0), right(0), data(0){}
   ~BinTree()
   {
      if(left) delete left;
      if(right) delete right;
      delete parent;
   }
   BinTree* insert(T, BinTree*);
   T search(T data);
   
private:
   BinTree*parent;
   BinTree*left;
   BinTree*right;
   T data;
};
 
BinTree* BinTree<T>::insert(T elem, BinTree* Tree)
{
    if(!Tree)
    {
        Tree=new BinTree[sizeof(BinTree)];
        Tree->data=elem;
        Tree->left=0;
        Tree->right=0;
    }
    else if(elem<Tree->data) Tree->left=insert(elem, Tree->left);
    else Tree->right=insert(elem, Tree->right);
    return Tree;
}
 
//Класс для итераторов
Добавлено через 3 часа 17 минут
Никто ничего подсказать не может? Я собственно вроде бы сделал insert. Выше в коде он описан. Мог ошибиться, писал по памяти. Чисто в теории верно или нет? И все же вопрос как подойти к этому (особенно с итератором, а еще более особенно что дерево как бы должен быть контейнер, а не n деревьев...).
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
06.09.2010, 23:40     Алгоритм реализации двоичного дерева #2
ну представляю себе так:
контейнер как минимум реализует begin,end
begin указывает на корень, end показывает, что текущаю позиция - следующий элемент после листа
доступ к кажому элементу - только через итератор
итератор реализует
iterator& iterator::left();
iterator& iterator::right();
T& iterator::operator*();
T* iterator::operator->();

сама реализация бинарного дерева довольно классическая
только вот смысл реализовывать по типу STL, все равно не понятно каким образом можно будет применить алгоритмы или что-нибудь в этом духе
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
06.09.2010, 23:50  [ТС]     Алгоритм реализации двоичного дерева #3
alex_x_x, Спасибо. Думаю стоит мне отказаться от этого задания. Знаний реализовать может и хватит, но вот времени уйдет неоправданно много. Тем более, что это не слишком-то и нужно.
Спасибо.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
06.09.2010, 23:51     Алгоритм реализации двоичного дерева #4
если интересует дерево
то
struct{
T* left
T* right;
};

корень
parent = new T(); //для T необходим дефолтовый конструктор

C++
1
2
3
4
5
6
7
iterator insert_left( iterator& it, const T t ){
  if( it->left ){
    return end();
  }
  it->left = new T( t );
  return iterator( it->left );
}
ну както так

Добавлено через 1 минуту
Lavroff, ну это довольно интересно
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
07.09.2010, 00:07  [ТС]     Алгоритм реализации двоичного дерева #5

Не по теме:

alex_x_x, Да я знаю. Ща учеба началась. Напряги пойдут и т.д. Много времени за этим просиживать не будет, а потому будет отодвигаться все дальше и дальше. А я так не слишком люблю делать. Но впринципе, ради интереса попробую что-то поделать.



Добавлено через 11 минут
Тему можно клоузнуть до лучших времен.
Yandex
Объявления
07.09.2010, 00:07     Алгоритм реализации двоичного дерева
Ответ Создать тему
Опции темы

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