Модераторы: bsa

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> удаление узла в bt 
V
    Опции темы
afanp
Дата 21.3.2009, 17:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет
совсем уже запутался, не получается удалить узел. пока только если нет правого или левого потомка.
Код


void remove(tree*&beginroot,int a){
    tree*pv=beginroot;
    bool found=0;
    while(pv && !found){
        if(a > pv->value) pv=pv->right;
        if(a < pv->value) pv=pv->left;
        if(a==pv->value) found=true;
    }
    if(found){
        if(pv->left==0){
            tree*another=pv;
            pv=another->right;
            pv->right=0;
            delete another;}
    }
}

вот отрывок если нет левого потомка. почему-то не удаляется  smile 
вернее так удаляется но потом при просмотре какая-то херата, получается ошибка )

Это сообщение отредактировал(а) afanp - 21.3.2009, 17:56
PM MAIL   Вверх
andrew_121
Дата 21.3.2009, 18:17 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Кодофей
****


Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 10
Всего: 33
Тяжко мне сейчас думать. Суббота все-же smile  Давай до Понедельника отложим?  smile 


--------------------
Удалил аккаунт. Прощайте!
PM MAIL   Вверх
zim22
Дата 21.3.2009, 18:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69
afanp, лови универсальный метод решения:
1) находим ручку
2) находим листик
3) рисуем пошагово, как алгоритм работает
4) много думаем


--------------------
C++ FAQ Lite
PM MAIL   Вверх
mes
Дата 21.3.2009, 19:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250
Цитата(zim22 @  21.3.2009,  17:58 Найти цитируемый пост)
afanp, лови универсальный метод решения:

и как подсказка, подумайте на кого в результате указывает предыдущий (относительно удаляемого) элемент  smile


--------------------
http://opendots.net
PM MAIL WWW   Вверх
afanp
Дата 21.3.2009, 21:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет
спасибо большое за подсказки. буду думать.если че напишу
PM MAIL   Вверх
afanp
Дата 22.3.2009, 11:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет
Сделал вот так. Если вдруг что неправильно, подскажите?
Код

void remove(tree*&beginroot,int a){
    bool found=0;
    tree*root=beginroot;
    tree*prev=beginroot;
    while(root && !found){
        prev=root;
        if(a > root->value) root=root->right;
        if(a < root->value) root=root->left;
        if(a==root->value) found=true;
    }
    if(found){
        bool path=0,poka=0;
        if(prev->right==root){
            path=1;}
        if(root->left==0 && !poka){
            tree*another=root;
            root=another->right;
            poka=true;
            delete another;}
        if(root->right==0 && !poka){
            tree*another=root;
            root=another->left;
            poka=true;
            delete another;}
        if(root->right && root->left && !poka){
            tree*another=root;
            root=another->left;
            root->right=another->right;
            poka=true;}
        if(path) prev->right=root;
        else prev->left=root;
    }
PM MAIL   Вверх
mes
Дата 22.3.2009, 13:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250
Цитата(afanp @  22.3.2009,  10:41 Найти цитируемый пост)
    tree*prev=beginroot;
    while(root && !found){
        prev=root;
        if(a > root->value) root=root->right;
        if(a < root->value) root=root->left;
        if(a==root->value) found=true;
    }
    if(found){

вначале должны провереть первую ветку потом спускаемся  дальше,
а предыдущий изначально NULL

вот поправка :
Код

    tree*prev=NULL;
    for (;root && a!=root->value;  prev=root ) {
        if(a > root->value) root=root->right;
        if(a < root->value) root=root->left;
    }
    if (root) { //  вместо if (found)

ну и дальше поправить с учетом вышенаписанного smile судя по всему у самого должно получиться, успехов smile

Это сообщение отредактировал(а) mes - 22.3.2009, 13:32


--------------------
http://opendots.net
PM MAIL WWW   Вверх
afanp
Дата 22.3.2009, 16:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет
mes,  насколько правильно понял я ваш код, то я могу впринципе обойтись и своим?
<quote="mes">
вначале должны провереть первую ветку потом спускаемся  дальше,
</quote>
немного не понял этого.
Код

  tree*root=beginroot;
    tree*prev=beginroot;
    while(root && !found){
        prev=root;
        if(a > root->value) root=root->right;
        if(a < root->value) root=root->left;
        if(a==root->value) found=true;
    }

здесь же я проверяю все "ярусы" начиная от первого ? разве нет?
PM MAIL   Вверх
mes
Дата 22.3.2009, 16:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250
Цитата(afanp @  22.3.2009,  15:28 Найти цитируемый пост)
здесь же я проверяю все "ярусы" начиная от первого ? разве нет?

нет

Цитата(afanp @  22.3.2009,  15:28 Найти цитируемый пост)
    while(root && !found){
        prev=root; //  запомнили текущий
        if(a > root->value) root=root->right; // перешли к правому 
        if(a < root->value) root=root->left;  // или левому
        if(a==root->value) found=true; // проверили , после того как перешли.. самый первый элемент остался без проверки.
    }




--------------------
http://opendots.net
PM MAIL WWW   Вверх
afanp
Дата 23.3.2009, 13:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет
mes,  спасибо большое ! кажется на уровне теории разобрался. сейчас приду из бассейна и попытаюсь воплотить в жизнь)
PM MAIL   Вверх
zim22
Дата 23.3.2009, 13:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69
 smile 
Цитата(afanp @  23.3.2009,  13:22 Найти цитируемый пост)
сейчас приду из бассейна

а что, после бассейна лучше программируется?


--------------------
C++ FAQ Lite
PM MAIL   Вверх
afanp
Дата 23.3.2009, 16:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет
zim22, 
да
PM MAIL   Вверх
zim22
Дата 23.3.2009, 16:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69
 smile 
эхх. нет бассейна поблизости. пойду воды попью smile


--------------------
C++ FAQ Lite
PM MAIL   Вверх
afanp
Дата 24.3.2009, 19:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет
кажется я подошел к самому отвественному моменту - удаление узла с 2мя потомками. Я так думаю, удалять узел, все что справа одно дерево, все что слева - другое. Затем два этих дерева объединять и пытатся всунуть в основное. Пральна?   smile 
потом это еще как класс нужно сделать будет, я не думаю что с этим могут быть проблемы, или я неправ?

Это сообщение отредактировал(а) afanp - 24.3.2009, 19:21
PM MAIL   Вверх
mes
Дата 24.3.2009, 20:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 79
Всего: 250
Цитата(afanp @  24.3.2009,  18:19 Найти цитируемый пост)
Я так думаю, удалять узел, все что справа одно дерево, все что слева - другое. Затем два этих дерева объединять и пытатся всунуть в основное. Пральна?   smile 

вначале вставить одну ветку на место удаленного элемента, а потом в нее вставить другую. smile

Добавлено через 1 минуту и 49 секунд
Цитата(afanp @  24.3.2009,  18:19 Найти цитируемый пост)
кажется я подошел к самому отвественному моменту - удаление узла с 2мя потомками.

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



--------------------
http://opendots.net
PM MAIL WWW   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1156 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.