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

Итератор для бинарного дерева поиска. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.83
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
24.05.2011, 16:39     Итератор для бинарного дерева поиска. #1
Господа, нужен совет знатоков. Бинарное дерево поиска представлено следующей структурой.

C++
1
2
3
4
5
6
template <typename ValueType>
struct Node {
  ValueType value;
  Node *left;
  Node *right;
}
Вопрос заключается в следующем: каким образом реализуется итератор (хотя бы однонаправленный) для такой структуры?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.05.2011, 16:39     Итератор для бинарного дерева поиска.
Посмотрите здесь:

C++ (ищу) Алгоритм построения бинарного дерева поиска
Распечатка бинарного дерева поиска C++
Итератор для бинарного дерева C++
Создание бинарного дерева поиска C++
C++ Реализация бинарного дерева поиска
C++ Удаления узла из бинарного дерева поиска
C++ Итератор дерева бинарного поиска
C++ Удаление элементов из бинарного дерева (не дерево поиска)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
24.05.2011, 20:15     Итератор для бинарного дерева поиска. #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Если вид структуры именно такой( нет указателя на родительский узел ), то обычно обход можно сделать с использованием стека, запоминая пройденные узлы. Быстренько набросал примерчик, корявый , но суть описывает(только префиксный ++):
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 <stack>
 
template <typename ValueType>
struct Node {
    ValueType value;
    Node *left;
    Node *right;
    };
 
template <typename ValueType>
struct pre_iterator;
 
template <typename ValueType>
struct iterator_base
    {
    std::stack<Node<ValueType> > node_stack;
    // constructors
    iterator_base()
        : node(0)
        {
        }
    iterator_base(Node<ValueType> * _node)
        : node(_node)
        {
        }
 
    // overloaded indirection operators
    ValueType & operator*() const
        {
        return node->value;
        }
 
    ValueType * operator->() const
        {
        return &node-value;
        }
 
    pre_iterator<ValueType> begin() const
        {
        if(node->left == 0)
            return end();
 
        return pre_iterator<ValueType>(node->left);
        }
 
    pre_iterator<ValueType> end() const
        {
        return pre_iterator<ValueType>(0);
        }
 
    Node<ValueType> * node;
    };
 
template <typename ValueType>
struct pre_iterator : public iterator_base<ValueType>
    {
    // constructors
    pre_iterator()
        : iterator_base(0)
        {
        }
 
    pre_iterator(Node<ValueType> * _node)
        : iterator_base(_node)
        {
        }
 
    pre_iterator(iterator_base<ValueType> const & other)
        : iterator_base(other.node)
        {
        }
 
    pre_iterator(pre_iterator<ValueType> const & other)
        : iterator_base(other.node)
        {
        }
 
    pre_iterator& operator++()
        {
        if(node->left != 0)
            {
            node_stack.push(*node);
            node = node->left;
            }
        else
            {
            while(node->right == 0)
                {
                *node = node_stack.top();
                                node_stack.pop();
                if(node == 0)
                    return *this;
                }
            node_stack.push(*node);
                        // если мы добрались до конца дерева, то возвращаем конечный итератор
            if(node == node->right)
                {
                *this = end();
                return *this;
                }
            node = node->right;
            }
        return *this;
        }
 
    };
Добавлено через 2 часа 25 минут
А вообще ведь я наврал с реализацией, неправильно работает, да и усложнил не по делу.
В стеке пройденных вершин достаточно хранить указатели на Node<ValueType>, в самом начале при инициализации итератора поместить в стек указатель на вершину дерева, а в ходе ++ получится совсем просто
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pre_iterator& operator++()
    {
     if(node != 0)
        {
        if(node->right != 0)
            {
            node_stack.push(node->right);
            }
        
        if(node->left != 0)
            {
            node = node->left;
            }
        else
            {
            node = node_stack.top();
            node_stack.pop();
            }
        }
    return *this;
    }
Yandex
Объявления
24.05.2011, 20:15     Итератор для бинарного дерева поиска.
Ответ Создать тему
Опции темы

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