Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.53/19: Рейтинг темы: голосов - 19, средняя оценка - 4.53
В астрале
Эксперт С++
8032 / 4789 / 655
Регистрация: 24.06.2010
Сообщений: 10,558
1

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

14.03.2011, 22:00. Показов 3419. Ответов 4
Метки нет (Все метки)

Кхм. Попытался реализовать итератор для обхода по бинарному дереву...
Наткнулся на запару. Дерево должно быть обязательно круговым, чтобы по нему можно было использовать нормальный итератор?

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
template<class T>
class Tree<T>::Tree_Iterator
{
public:
    Tree_Iterator():curr(0)
    {
    }
    Tree_Iterator(Node* curr_):
        curr(curr_)
    {
    }
    T& operator *() 
    {
        return curr->elem;
    }
    const T& operator *() const
    {
        return curr->elem;
    }
    Tree_Iterator operator ++()
    {
        Inc();
        return Tree_Iterator(curr);
    }
    bool operator ==(const Tree_Iterator& sec)
    {
        return curr == sec.curr;
    }
    bool operator !=(const Tree_Iterator& sec)
    {
        return !(*this == sec);
    }
private:
    Node* curr;
 
    std::stack<Node*> nodes;
    std::stack<Node*> for_reverse;
 
    void Inc()
    {
        while(curr)
        {
            nodes.push(curr);
            for_reverse.push(curr);
            curr=curr->_left;
            if(curr)
                return;
        }
        if(nodes.empty())
            return;
        while(!curr)
        {
            curr=nodes.top();
            nodes.pop();
            curr=curr->_right;
            if(curr)
                for_reverse.push(curr);
        }
    }
};
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    Node* find_max_right()
    {
        while(curr)
            curr=curr->_right;
        return curr;
    }
    iterator begin()
    {
        return iterator(curr);
    }
    iterator end()
    {
        return iterator(find_max_right());
    }
При end соответственно все плохо. Ибо идет ошибка, т.к. find_max_right возвращает ноль. В то же время если в find_max_right поставить while(curr->right) - последний элемент остается за бортом...
Как тут лучше всего сделать, чтобы обойтись меньшими жертвами? Спасибо.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.03.2011, 22:00
Ответы с готовыми решениями:

Итератор по бинарному дереву
Всем привет! Помогите пожалуйста! Пишу бинарное дерево, нужно реализовать итератор по нему. Не...

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

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

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

4
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
14.03.2011, 22:28 2
Лучший ответ Сообщение было отмечено ForEveR как решение

Решение

Я, как-то делая n-арное дерево, тоже озаботился такой проблемой и решил в конечном счете делать так: у каждого узла есть указатель на родителя, первого и последнего сына( в твоем случае левого и правого ), и плюс к тому еще указатель на левого и правого брата ( то бишь для левого узла ссылка на левого в NULL, а на правого всё ок, ну и наоборот для правого узла ). Далее довольно просто реализовать паттерн прохода итератора (кстати, "нормальный" - значит стандартный обход в глубину?), у меня выходило что-то в стиле
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
template<typename T,typename __tree_node_allocator>
typename Tree<T,__tree_node_allocator>::pre_order_iterator& 
Tree<T,__tree_node_allocator>::pre_order_iterator::operator++()
    {
        // текущий узел - валидный
    assert(this->node != NULL);
        // если пропускать сыновей не надо и первый сын - валидный 
    if(!this->__skip_current_children && this->node->my_first_child != NULL)
        {
                // двигаем позицию итератора на сына
        this->node = this->node->my_first_child;
        }
    else
        {
                // делать нечего, только возвращаться назад по дереву
        this->__skip_current_children = false;
        while(this->node->my_next_sibling == NULL)
            {
            this->node = this->node->my_parent;
                        // если уже всё дерево пройдено, то возвращаем end
            if(this->node == NULL)
                return *this;
            }
                // если правая ветка есть, то лезем на неё
        this->node = this->node->my_next_sibling;
        }
    return *this;
    }
Но дерево фактически остается циклическим, так как конец в принципе прицеплен к голове, только разве что сам узел не валидный.
1
В астрале
Эксперт С++
8032 / 4789 / 655
Регистрация: 24.06.2010
Сообщений: 10,558
14.03.2011, 22:42  [ТС] 3
Ma3a, Интересно... Надо будет создать новый проект исключительно с деревом и попробовать сделать так... Только для чего обязательно указатели на братьев?
0
Эксперт С++
623 / 467 / 57
Регистрация: 28.01.2011
Сообщений: 605
14.03.2011, 22:48 4
А так просто легче следить за тем, на какой ветке мы находимся, левой или правой, и соответственно (как мне кажется) обход по своей сути чисто алгоритмически сделать проще, особенно с возвратом по дереву и переходам на следующие ветки. Впрочем, для бинарного дерева может это и вовсе лишнее, но мне так удобнее мыслить структуру.

Добавлено через 3 минуты
Я еще писал всё это дело с учетом того, что будут поддерживаться несколько типов итераторов, типа пре-, пост-итераторов, в ширину, на одном уровне ну и прочее, вот и вышла необходимость в таких ссылках.
1
В астрале
Эксперт С++
8032 / 4789 / 655
Регистрация: 24.06.2010
Сообщений: 10,558
15.03.2011, 03:35  [ТС] 5
Это единственное предложение? Со стеками шаманить не вариант?

Добавлено через 2 часа 53 минуты
Чуть не убился с этим.
Вот что вышло в итоге.

Добавил в Node

C++
1
2
        Node* _parent;
        bool isChecked;
Исправил функцию.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        void insert_helper(T val)
        {
            if(val <= elem && _left)
                _left->insert_helper(val);
            else if(val <= elem && !_left)
            {
                _left=new Node(val);
                _left->_parent=this;
            }
            else if(val > elem && _right)
                _right->insert_helper(val);
            else
            {
                _right=new Node(val);
                _right->_parent=this;
            }
        }
C++
1
2
3
4
5
6
7
8
9
10
11
12
    void insert(T val)
    {
        if(!curr)
        {
            curr=new Node(val);
            curr->_parent=new Node;
            curr->_parent->_left=curr;
            curr->_parent->_right=curr;
        }
        else
            curr->insert_helper(val);
    }
C++
1
2
3
4
5
6
7
8
    iterator begin()
    {
        return iterator(find_max_left(curr));
    }
    iterator end()
    {
        return iterator(curr->_parent);
    }
C++
1
2
3
4
5
6
7
    Node* find_max_left(Node* tree_node)
    {
        if(tree_node->_left)
            return find_max_left(tree_node->_left);
        tree_node->isChecked=true;
        return tree_node;
    }
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
    void Inc()
    {
        int linkCnt=0;
        while(curr->_left)
        {
            if(curr->_left->isChecked)
                break;
            curr=curr->_left;
            ++linkCnt;
        }
        if(linkCnt)
        {
            curr->isChecked=true;
            return;
        }
        else
        {
            while(curr->_parent)
            {
                if(curr->_right)
                    if(!curr->_right->isChecked)
                        break;
                curr=curr->_parent;
            }
        }
        if(curr->_right && !curr->_right->isChecked)
            curr=curr->_right;
        linkCnt=0;
        while(curr->_left && !curr->_left->isChecked)
        {
            curr=curr->_left;
            ++linkCnt;
        }
        if(linkCnt)
        {
            curr->isChecked=true;
            return;
        }
        while(curr->_right && !curr->_right->isChecked)
            curr=curr->_right;
        curr->isChecked=true;
        return;
    }
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.03.2011, 03:35

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

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

Итератор дерева для обхода в ширину
Задано дерево вида struct Node { Node * parent; std::vector&lt;Node *&gt; sons; int data;...

Подробно разбираем задачу Обхода по дереву с применением reduce
Добрый вечер! Столкнулся с задачей, связанной с обходом по дереву. Прошу помочь разобраться!!!...

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


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

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

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