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

Бинарное дерево и класс итератора

09.11.2011, 06:15. Просмотров 702. Ответов 0
Метки нет (Все метки)

Доброго времени суток, помогите пожалуйста.
есть вот такая штуковина
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
template<typename T>
class bst{
    struct et{
        et* l;//лево
        et* r;//право
        int k;//ключ
        T v;//данные
 
        et();
        et(et&);
        et(int,int);
        ~et();
    };
    et * head;
    int count;//количество елементов
    int itcount;//количество просмотренных методом узлов
public:
    bst();
    bst(bst&);
    ~bst();
/*еще какие-то методы*/
    bool delkey(int);
 
    friend class it;
    class it{//класс итератора
        bst<T>* base;
        et* p;
    public:
        it(bst<T>*);
        bool beginkye();//установка на первый узел в дереве с минимальным ключом,
        bool endkey();//установка на последний узел в дереве с максимальным ключом,
        bool good();//проверка состояния итератора,
        T& operator *();//доступ по чтению и записи к данным текущего узла в дереве,
        bool next();//переход к следующему по значению ключа узлу в дереве,(ltr обход)
        bool prev();//переход к предыдущему по значению ключа узлу в дереве,(rtl обход)
    };
};
template<typename T>
bool bst<T>::delkey(int key){
    bst<T>::et* p=head;
    bst<T>::et* pp;
    itcount=1;
    while(1){//поиск
        pp=p;
        if(!p)return false;
        if(key==p->k)break;
        else if(key < p->k)p=p->l;
        else p=p->r;
        itcount++;
    }
 
    if(p->l && p->r){//если 2 потомка
        bst<T>::et* pr=p->r, ppr;
        for(;pr->l;ppr=pr, pr=pr->l, itcount++);//минимум справа
        bst<T>::et* pl=p->l, ppl;
        for(;pl->r;ppl=pl, pl=pl->r,itcount++);//максисум слева
        if(p->k - pl->k > pr->k - p->k){pl=pr; ppl=ppr;}//сравнение интервалов
        p->v=pl->v; p->k=pl->k;//изменение полей на бижайшие
        p=pl;//смена удаляемого указателя
        pp=ppl;//смена родителя
    }
 
    if(p->l){//левый потомок
        if(pp->l==p)pp->l=p->l;
        else pp->r=p->l;
        p->l=NULL;
    }
    else if(p->r){//правый потомок
        if(pp->l==p)pp->l=p->r;
        else pp->r=p->r;
        p->r=NULL;
    }
 
    delete p;
    count--;
    return true;
}
как написать
template<typename T>
bool bst<T>::it::good();
если учесть, что мы в любой момент можем удалить любй узел дерева, а указатель et* bst<T>::it:: p вполне может на нем оказаться...
причем даже если мы сохраним последнее значение указателя в long(при любом его перемещении), затем что-то сделаем с деревеом, т.е. удалим узел, то не факт, что при добавлении элемента система не подсунет нам тот же адрес...
как организовать проверку help me pleas...

Добавлено через 15 минут
в общем, дерево не знает об итераторе вообще, а итератор знает только структуру дерева...
и не хочется деать полный обход, и проверять адреса...
или создавать стэк удаленных адресов...

Добавлено через 22 часа 6 минут
додумался только до et** для итератора и занулении p при удалении)))
всем спасибо)
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
template<typename T>
class bst{
        struct et{
                et* l;//лево
                et* r;//право
                int k;//ключ
                T v;//данные
 
                et();
                et(et&);
                et(int,int);
                ~et();
        };
        et * head;
        int count;//количество елементов
        int itcount;//количество просмотренных методом узлов
public:
        bst();
        bst(bst&);
        ~bst();
/*еще какие-то методы*/
        bool delkey(int);
 
        friend class it;
        class it{//класс итератора
                bst<T>* base;
                et** p;//вот так вот и решил)))
        public:
                it(bst<T>*);
                bool beginkye();//установка на первый узел в дереве с минимальным ключом,
                bool endkey();//установка на последний узел в дереве с максимальным ключом,
                bool good();//проверка состояния итератора,
                T& operator *();//доступ по чтению и записи к данным текущего узла в дереве,
                bool next();//переход к следующему по значению ключа узлу в дереве,(ltr обход)
                bool prev();//переход к предыдущему по значению ключа узлу в дереве,(rtl обход)
        };
};
template<typename T>
bool bst<T>::delkey(int key){
        bst<T>::et* p=head;
        bst<T>::et* pp;
        itcount=1;
        while(1){//поиск
                pp=p;
                if(!p)return false;
                if(key==p->k)break;
                else if(key < p->k)p=p->l;
                else p=p->r;
                itcount++;
        }
 
        if(p->l && p->r){//если 2 потомка
                bst<T>::et* pr=p->r, ppr;
                for(;pr->l;ppr=pr, pr=pr->l, itcount++);//минимум справа
                bst<T>::et* pl=p->l, ppl;
                for(;pl->r;ppl=pl, pl=pl->r,itcount++);//максисум слева
                if(p->k - pl->k > pr->k - p->k){pl=pr; ppl=ppr;}//сравнение интервалов
                p->v=pl->v;     p->k=pl->k;//изменение полей на бижайшие
                p=pl;//смена удаляемого указателя
                pp=ppl;//смена родителя
        }
 
        if(p->l){//левый потомок
                if(pp->l==p)pp->l=p->l;
                else pp->r=p->l;
                p->l=NULL;
        }
        else if(p->r){//правый потомок
                if(pp->l==p)pp->l=p->r;
                else pp->r=p->r;
                p->r=NULL;
        }
 
        delete p;
        p=NULL;//собственно тогда при разымнеовании bst<T>::it::p получим NULL, что и требовалось
        count--;
        return true;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2011, 06:15
Ответы с готовыми решениями:

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в...

Класс бинарное дерево
Здравствуйте. Требуется написать англо-русский словарь на основе бинарного...

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

Нужно реализовать класс Бинарное дерево.
Нужно реализовать класс Бинарное дерево. Вот класс template &lt;class T&gt; class...

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.11.2011, 06:15

Создать шаблонный класс «бинарное дерево»
Создать шаблон класса «бинарное дерево». Использовать его для сортировки целых...

Создать шаблонный класс «бинарное дерево»
Создать шаблон класса «бинарное дерево». Использовать его для сортировки целых...

Описать класс, что реализует бинарное дерево
Доброго времени суток. Может кто-то поделиться готовым кодом или примером для...


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

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

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