IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Двоичное дерево: Удаление листьев, не имеющих соседей., Покажите пожалуйста, как переделать процедуру.
mind abuse
сообщение 16.05.2008 0:10
Сообщение #1


Студент
*

Группа: Пользователи
Сообщений: 35
Пол: Мужской
Реальное имя: Владимир

Репутация: -  3  +


Суть проблемы такова: в приложенном файле есть здоровое красивое бинарное дерево с многими удобствами, включая рисование самого себя /*не помню, где скачал, авторство, кажется, то ли volvo, то ли другого пользователя*/ и в нём есть процедура удаления элемента:

procedure delelem(var root:PTree;info:byte);
var temp:PTree;
begin
if (root<>NIL) then (* Если дерево не пустое, то *)
begin
if (info<root^.info) then (* Если удаляемый элемент меньше тек. узла, то *)
delelem(root^.left,info) (* Удалить его из левого поддерева *)
else (* Иначе *)
if (info>root^.info) then (* Если удаляемый элемент больше тек. узла, то *)
delelem(root^.right,info) (* Удалить его из правого поддерева *)
else (* Иначе тек. узел - удаляемый элемент *)
begin
if (root^.left=NIL) and (root^.right=NIL) then (* Если тек. узел - лист, то *)
begin
dispose(root); (* Удалить его *)
root:=NIL; (* Поставить на его место пустое дерево *)
end
else
if (root^.left=NIL) and (root^.right<>NIL) then
(* Если у тек.узла есть только правая ветвь *)
begin
temp:=root; (* Присоединить её вместо тек. узла *)
root:=root^.right;
dispose(temp); (* Удалить тек. узел *)
end
else
if (root^.left<>NIL) and (root^.right=NIL) then
(* Если у тек.узла есть только левая ветвь *)
begin
temp:=root; (* Присоединить её вместо тек. узла *)
root:=root^.left;
dispose(temp); (* Удалить тек. узел *)
end
else (* Иначе у узла есть обе ветви *)
begin
root^.info:=getmostright(root^.left);
(* Вставить на место узла самый правый эл-т левого поддерева *)
delelem(root^.left,root^.info);
(* Удалить самый правый эл-т из левого поддерева *)
end;

end;
end;
end;
Покажите пожалуйста, как переделать её в удаление только листьев, не имеющих соседей.


Прикрепленные файлы
Прикрепленный файл  tree.pas ( 11.08 килобайт ) Кол-во скачиваний: 222


--------------------
...Чего-то хотелось: не то конституции, не то севрюжины с хреном, не то кого-нибудь ободрать.
(М. Е. Салтыков-Щедрин)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 4)
volvo
сообщение 16.05.2008 0:24
Сообщение #2


Гость






Нет, это программа не моя, это демонстрационная программа по работе с деревьями из FAQ-а форума...

Можно уточнить, что значит,
Цитата
удаление только листьев, не имеющих соседей.
? Какие листья имеют соседей? Определение "соседства" можно привести?
 К началу страницы 
+ Ответить 
mind abuse
сообщение 16.05.2008 0:51
Сообщение #3


Студент
*

Группа: Пользователи
Сообщений: 35
Пол: Мужской
Реальное имя: Владимир

Репутация: -  3  +


Я подразумеваю лист как узел, не имеющий потомков, соответственно, если от узла b отходят листья a и c, то мы их не трогаем, если только a - удаляем его.


--------------------
...Чего-то хотелось: не то конституции, не то севрюжины с хреном, не то кого-нибудь ободрать.
(М. Е. Салтыков-Щедрин)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 16.05.2008 2:25
Сообщение #4


Гость






По-моему, нигде не ошибся, проверь:
procedure del_leafs(var root: ptree);

function is_leaf(p: ptree): boolean;
begin
is_leaf := (p <> nil) and (p^.right = nil) and (p^.left = nil);
end;

begin
if root <> nil then begin

if (root^.left = nil) then
if is_leaf(root^.right) then begin
dispose(root^.right); root^.right := nil; exit;
end;

if (root^.right = nil) then
if is_leaf(root^.left) then begin
dispose(root^.left); root^.left := nil; exit;
end;

del_leafs(root^.left);
del_leafs(root^.right);
end;
end;
 К началу страницы 
+ Ответить 
mind abuse
сообщение 17.05.2008 10:44
Сообщение #5


Студент
*

Группа: Пользователи
Сообщений: 35
Пол: Мужской
Реальное имя: Владимир

Репутация: -  3  +


Спасибо! Всё весьма наглядно работает /*хоть на проверку этого сломавшийся компьютер отдал лишь последнтие пять минут своей жизни*/


--------------------
...Чего-то хотелось: не то конституции, не то севрюжины с хреном, не то кого-нибудь ободрать.
(М. Е. Салтыков-Щедрин)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 22.06.2025 0:06
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"