Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
1evgen1111
0 / 0 / 0
Регистрация: 04.02.2019
Сообщений: 3
1

Итератор по бинарному дереву

04.02.2019, 20:51. Просмотров 396. Ответов 5
Метки нет (Все метки)

Всем привет! Помогите пожалуйста!
Пишу бинарное дерево, нужно реализовать итератор по нему. Не очень понимаю, как это грамотно сделать(
Вот мой код:
C++ (Qt)
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
template <typename T>
class Tree {
private:
    struct Node {
        Node() : left(nullptr), right(nullptr) {}
        T data;
        Node *left, *right;
    };
    Node* root;
    void makeNode(Node** node, T data_) {
        if (!(*node)) {
            Node* new_node = new Node;
            new_node->data = data_;
            *node = new_node;
        }
        else {
            if (((*node)->data < data_))
                makeNode(&((*node)->left), data_);
            else makeNode(&((*node)->right), data_);
        }
    }
 
public:
    Tree() :root(nullptr) {}
    void add(const T& val_) {
        makeNode(&root, val_);
    }
    
    class Iterator {
        private:
                Node * it_node;
    public:
        Iterator(Node* root) :  it_node(root) {}
 
        bool operator!=(Iterator const & other) const
        {
        }
 
        T &operator*() const {
        }
 
 
        Iterator operator++()
        {}
 
    };
    Iterator begin() {
        return Iterator(root);
    }
    Iterator end() {
        return Iterator(NULL);
 
    }
};

Помогите пожалуйста, как правильно реализовать операторы *, ++, ==, != ?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2019, 20:51
Ответы с готовыми решениями:

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

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

Поиск по бинарному дереву целочисленных значений
Здравствуйте! Очень нужна помощь данном, надеюсь что простом, задании. Заранее спасибо!:-[ ...

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

Реализовать двусвязный список (list), итератор (iterator) и константный итератор (сonst_iterator) для списка
не могу понять что должно быть результатом. может подскажете примеры? пожалуйста. Задание:...

5
jugu
213 / 138 / 26
Регистрация: 11.01.2019
Сообщений: 552
04.02.2019, 22:32 2
А почему класс итератора вложен в класс дерева? В чем смысл такого паттерна? Может имеет смысл параметризовать дерево типом итератора? Тогда можно перебирать элементы дерева разными итераторами, например, слева направо и справа налево.
0
Renji
2513 / 1719 / 515
Регистрация: 05.06.2014
Сообщений: 4,978
05.02.2019, 00:02 3
Цитата Сообщение от 1evgen1111 Посмотреть сообщение
Пишу бинарное дерево, нужно реализовать итератор по нему. Не очень понимаю, как это грамотно сделать(
Гугл, "Прошитое двоичное дерево".
Цитата Сообщение от jugu Посмотреть сообщение
А почему класс итератора вложен в класс дерева? В чем смысл такого паттерна?
Если он не будет вложен в дерево, будет много сексу с опережающим объявлением классов (итератор лезет в дерево, дерево лезет в итератор) и выносом тела методов за пределы объявления класса.
Цитата Сообщение от jugu Посмотреть сообщение
Тогда можно перебирать элементы дерева разными итераторами, например, слева направо и справа налево.
Для этого уже есть std::reverse_iterator.
0
jugu
213 / 138 / 26
Регистрация: 11.01.2019
Сообщений: 552
05.02.2019, 10:14 4
Цитата Сообщение от Renji Посмотреть сообщение
Если он не будет вложен в дерево, будет много сексу с опережающим объявлением классов (итератор лезет в дерево, дерево лезет в итератор) и выносом тела методов за пределы объявления класса.
Ну и ничего. Объявил - и всё! Это ж одна строчка. А так придется для каждого нового класса дерева городить свой вложенный класс итератора. Если, например, будет тернарное дерево? Или n-арное...

Добавлено через 1 минуту
Цитата Сообщение от Renji Посмотреть сообщение
Для этого уже есть std::reverse_iterator.
А если надо дерево по уровням пройти? Не припомню, чтоб был std::forward_level_iterator
0
Renji
2513 / 1719 / 515
Регистрация: 05.06.2014
Сообщений: 4,978
05.02.2019, 10:59 5
Цитата Сообщение от jugu Посмотреть сообщение
Ну и ничего. Объявил - и всё! Это ж одна строчка. А так придется для каждого нового класса дерева городить свой вложенный класс итератора. Если, например, будет тернарное дерево? Или n-арное...
Ну так сделайте N аргументом шаблона и соберите все деревья в один универсальный класс "N-арное дерево". После чего у вас и дерево будет объявлено один раз, и итератор внутри него будет объявлен один раз.
Цитата Сообщение от jugu Посмотреть сообщение
А если надо дерево по уровням пройти?
А какая в прошитом дереве разница? Все равно код итератора будет состоять из одной сиротливой строчки
C++
1
node=node->next
. Ладно, если вам нужно несколько разных итераторов, тогда
C++
1
node=node->next[IteratorID]
.
0
1evgen1111
0 / 0 / 0
Регистрация: 04.02.2019
Сообщений: 3
07.02.2019, 19:54  [ТС] 6
Класс итератор вложен в класс дерева, потому что такое задание.
Вообще нужно реализовать bidirectional iterator, то есть, насколько я понимаю, нужно еще реализовать оператор --.
Вот с этим у меня и проблема, не понимаю как обойти дерево и реализовать операторы (это тоже одно из условий задания - делать через операторы)
С односвязным списком быстро получилось, а тут не знаю, ступор))
0
07.02.2019, 19:54
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2019, 19:54

Ошибка в бинарному поиску
Много было тем про бинарный поиск.Я их посмотрел.Где ошибка в моем коде #include&lt;iostream&gt;...

Перемещение по бинарному файлу
Перемещаться можно по файлу использую функции seekg() для чтения и seekp() для записи... В общем...

Применить XOR к бинарному файлу
Добрый день, прошу помочь. Имеется некий массив бинарных данных, точнее файл - который надо...


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

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

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