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

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

04.02.2019, 20:51. Просмотров 870. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.02.2019, 20:51
Ответы с готовыми решениями:

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

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

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

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

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
5
588 / 396 / 148
Регистрация: 11.01.2019
Сообщений: 1,644
04.02.2019, 22:32 2
А почему класс итератора вложен в класс дерева? В чем смысл такого паттерна? Может имеет смысл параметризовать дерево типом итератора? Тогда можно перебирать элементы дерева разными итераторами, например, слева направо и справа налево.
0
2712 / 1879 / 556
Регистрация: 05.06.2014
Сообщений: 5,457
05.02.2019, 00:02 3
Цитата Сообщение от 1evgen1111 Посмотреть сообщение
Пишу бинарное дерево, нужно реализовать итератор по нему. Не очень понимаю, как это грамотно сделать(
Гугл, "Прошитое двоичное дерево".
Цитата Сообщение от jugu Посмотреть сообщение
А почему класс итератора вложен в класс дерева? В чем смысл такого паттерна?
Если он не будет вложен в дерево, будет много сексу с опережающим объявлением классов (итератор лезет в дерево, дерево лезет в итератор) и выносом тела методов за пределы объявления класса.
Цитата Сообщение от jugu Посмотреть сообщение
Тогда можно перебирать элементы дерева разными итераторами, например, слева направо и справа налево.
Для этого уже есть std::reverse_iterator.
0
588 / 396 / 148
Регистрация: 11.01.2019
Сообщений: 1,644
05.02.2019, 10:14 4
Цитата Сообщение от Renji Посмотреть сообщение
Если он не будет вложен в дерево, будет много сексу с опережающим объявлением классов (итератор лезет в дерево, дерево лезет в итератор) и выносом тела методов за пределы объявления класса.
Ну и ничего. Объявил - и всё! Это ж одна строчка. А так придется для каждого нового класса дерева городить свой вложенный класс итератора. Если, например, будет тернарное дерево? Или n-арное...

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

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

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

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

Особый итератор словаря. Итератор возвращающий нужные комбинации
Немогу разобраться, как написать итератор. У меня есть словарь, ключи это координаты, а значения...

Особый итератор словаря. Медленный итератор
Не могу разобраться, как написать итератор. У меня есть словарь, ключи это координаты, а значения...


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

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

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