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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
14.03.2011, 22:00     итератор для обхода по бинарному дереву #1
Кхм. Попытался реализовать итератор для обхода по бинарному дереву...
Наткнулся на запару. Дерево должно быть обязательно круговым, чтобы по нему можно было использовать нормальный итератор?

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) - последний элемент остается за бортом...
Как тут лучше всего сделать, чтобы обойтись меньшими жертвами? Спасибо.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.03.2011, 22:00     итератор для обхода по бинарному дереву
Посмотрите здесь:

Довести до ума программу про бинарному дереву C++
Итератор для бинарного дерева C++
Итератор для списка C++
Итератор для массива C++
Поиск по бинарному дереву целочисленных значений C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
14.03.2011, 22:28     итератор для обхода по бинарному дереву #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Я, как-то делая 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;
    }
Но дерево фактически остается циклическим, так как конец в принципе прицеплен к голове, только разве что сам узел не валидный.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
14.03.2011, 22:42  [ТС]     итератор для обхода по бинарному дереву #3
Ma3a, Интересно... Надо будет создать новый проект исключительно с деревом и попробовать сделать так... Только для чего обязательно указатели на братьев?
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
14.03.2011, 22:48     итератор для обхода по бинарному дереву #4
А так просто легче следить за тем, на какой ветке мы находимся, левой или правой, и соответственно (как мне кажется) обход по своей сути чисто алгоритмически сделать проще, особенно с возвратом по дереву и переходам на следующие ветки. Впрочем, для бинарного дерева может это и вовсе лишнее, но мне так удобнее мыслить структуру.

Добавлено через 3 минуты
Я еще писал всё это дело с учетом того, что будут поддерживаться несколько типов итераторов, типа пре-, пост-итераторов, в ширину, на одном уровне ну и прочее, вот и вышла необходимость в таких ссылках.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
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;
    }
Yandex
Объявления
15.03.2011, 03:35     итератор для обхода по бинарному дереву
Ответ Создать тему
Опции темы

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