Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Удаление поддерева 
V
    Опции темы
mChief
Дата 27.12.2008, 20:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Нужен предикат для удаления поддерева из двоичного дерева начиная  с заданой вершины.

Это сообщение отредактировал(а) mChief - 27.12.2008, 20:01
PM MAIL   Вверх
Фантом
Дата 27.12.2008, 20:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Вы это прекратите!
***


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

Репутация: 6
Всего: 49
А в каком виде хранится дерево?
PM   Вверх
mChief
Дата 28.12.2008, 00:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Забыл написать

tree=inttree(integer,inttree,inttree);end
PM MAIL   Вверх
Фантом
Дата 28.12.2008, 02:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Вы это прекратите!
***


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

Репутация: 6
Всего: 49
Ну так очевидно же:
Код

deltree(end,_,end).
deltree(A,N,B):-A=inttree(N,_,_),B=end,!.
deltree(A,N,B):-A=inttree(M,A1,A2),deltree(A1,N,B1),deltree(A2,N,B2),B=inttree(M,B1,B2).
PM   Вверх
mChief
Дата 28.12.2008, 14:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Спасибо
PM MAIL   Вверх
mChief
Дата 28.12.2008, 20:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Можно еще ворос. Как удалить один элемент и при этом перераспределить все элементы которые были ниже?
PM MAIL   Вверх
Фантом
Дата 28.12.2008, 20:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Вы это прекратите!
***


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

Репутация: 6
Всего: 49
Перераспределить куда? Ниже два поддерева, поэтому способ перераспределения неочевиден.
PM   Вверх
mChief
Дата 28.12.2008, 21:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Будем считать что дерево упорядоченное, например меньшие слева, большие справа. Тогда все элементы из нижних поддеревьев распределить по этому правилу

Это сообщение отредактировал(а) mChief - 28.12.2008, 21:25
PM MAIL   Вверх
Фантом
Дата 28.12.2008, 23:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Вы это прекратите!
***


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

Репутация: 6
Всего: 49
Это все равно неоднозначное условие. Ну, например, есть вершины с номерами 1,2,3 - в какое дерево их надо собрать?
PM   Вверх
mChief
Дата 29.12.2008, 04:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

Репутация: нет
Всего: нет
Условие однозначное, это бинарное дерево. Вершины 1,2,3 соберутся в дерево:
Код

                 1
                       2
                            3

если бы порядок был, например, 2,1,3 то получилось бы:
Код

                      2
                1         3

Кстати решение нашел, может кому пригодится
Код

 Вспомогательный предикат, удаляющий минимальный элемент бинарного дерева.
delete1 (tr (nil, Y, R), Y, R).
/* Если левое поддерево пусто, то минимальный элемент - корень, а дерево без
 минимального элемента - это правое поддерево.*/
delete1 (tr (L, K, R), Y, tr (L1, K, R)):-
     delete1 (L, Y, L1).
/* Левое поддерево не пусто, значит, оно содержит минимальное значение всего
 дерева, которое нужно удалить */
    Основной предикат, выполняющий удаление вершины из дерева, будет выглядеть следующим образом.

delete (tr (nil, X, R), X, R, 0):-
     nl, write ("Элемент из дерева удален.").
/* X совпадает с корневым значением исходного дерева, левое  поддерево пусто */
delete (tr (L, X, nil), X, L, 0):-
     nl,write("Элемент из дерева удален.").
/* X совпадает с корневым значением исходного дерева, правое поддерево пусто */
delete (T, _, T, 1):-
     nl,write ("Такого элемента нет!!!").
/*четвертый аргумент 1, поэтому такого элемента в дереве нет.*/
delete (tr (L, X, R), X, tr (L, Y, R1), _):-
     delete1(R,Y,R1).
/* X совпадает с корневым значением исходного дерева, причем ни левое,
 ни правое поддеревья не пусты */
delete (tr (L, K, R), X, tr (L1, K, R), H):-
     X<K,
     delete(L,X,L1,H).
/* X меньше корневого значения дерева */
delete (tr (L, K, R), X, tr (L, K, R1), H):-
     X>K,
     delete (R, X, R1, H).
/* X больше корневого значения дерева */
PM MAIL   Вверх
Фантом
Дата 30.12.2008, 02:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Вы это прекратите!
***


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

Репутация: 6
Всего: 49
А, ясно. Стормозил.  smile 
PM   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума Prolog
Void
  • Пожалуйста, создавайте темы с содержательными названиями.
  • Уважаемые учащиеся, здесь всегда рады помочь Вам, но не делать за Вас вашу работу. У вас гораздо больше шансов получить помощь, если Вы приложите усилия и поделитесь с нами проблемами и результатами. В противном случае добро пожаловать в раздел Центр Помощи.
  • Получив ответ на интересующий Вас вопрос, не забудьте пометить его как решённый.

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

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


 




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


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

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