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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 5.00
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
#1

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

06.09.2010, 23:40. Просмотров 4093. Ответов 4
Метки нет (Все метки)

Нужно написать реализацию двоичного дерева с использованием шаблонов в упрощенном виде следуя конвенциям 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 деревьев...).
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.09.2010, 23:40
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм реализации двоичного дерева (C++):

Пример двоичного дерева - C++
Здравствуйте! Возникла мысль попробовать реализовать двоичное дерево в c++ для этого решил сначала рассмотреть какие-нибудь примеры в...

Проверка корректности двоичного дерева - C++
Здравствуйте! Задача такая, Свойство двоичного дерева поиска можно сформулировать следующим образом: для каждой вершины дерева V...

Удаление корня двоичного дерева - C++
двоичное дерево состоит только из ptr корень двоичного дерева как удалить этот корень?

Вывести все вершины двоичного дерева - C++
Двоичное дерево задано в виде: m,g],s,y]] Как с помощью стека вывести это на экран? Набросайте, кому не трудно алгоритм) просто...

Помогите сделать обход двоичного дерева - C++
Есть некий проект (большой, несколько файлов), где происходит процессы со списком (добавление, удаление и т. д.). Структура: /** *...

Как можно совершить обход двоичного дерева нерекурсивно - C++
Доброго времени суток. Хочу поинтересоваться: как можно совершить обход двоичного дерева нерекурсивно(!!!), желательно с примерами или...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
06.09.2010, 23:40 #2
ну представляю себе так:
контейнер как минимум реализует begin,end
begin указывает на корень, end показывает, что текущаю позиция - следующий элемент после листа
доступ к кажому элементу - только через итератор
итератор реализует
iterator& iterator::left();
iterator& iterator::right();
T& iterator::operator*();
T* iterator::operator->();

сама реализация бинарного дерева довольно классическая
только вот смысл реализовывать по типу STL, все равно не понятно каким образом можно будет применить алгоритмы или что-нибудь в этом духе
1
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
06.09.2010, 23:50  [ТС] #3
alex_x_x, Спасибо. Думаю стоит мне отказаться от этого задания. Знаний реализовать может и хватит, но вот времени уйдет неоправданно много. Тем более, что это не слишком-то и нужно.
Спасибо.
0
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
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, ну это довольно интересно
1
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
07.09.2010, 00:07  [ТС] #5

Не по теме:

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



Добавлено через 11 минут
Тему можно клоузнуть до лучших времен.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2010, 00:07
Привет! Вот еще темы с ответами:

Создать класс [B]TreeChar[/B], для работы с элементами двоичного дерева - C++
Создать класс TreeChar, для работы с элементами двоичного дерева ASCII-символов. В качестве членов-данных рекомендуется брать элементы...

Англо-русский словарь построен в виде двоичного дерева в программе с++ - C++
Англо-русский словарь построен в виде двоичного дерева. Каждая компонента содержит английское слово, соответствующее ему русское слово и...

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
07.09.2010, 00:07
Ответ Создать тему
Опции темы

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