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

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

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

 
 Ответить  Открыть новую тему 
> Удаление листьев дерева
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

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


Есть задача. Имеется бинарное дерево. Информация в узлах не важна (могут быть цифры, могут быть буквы).
Задание: Удалить все листья дерева.

Допустим делаем обход
Procedure obhod(p:tree); 
Begin
if p<>nil then
begin
obhod(p^.left);
writeln(p^.inf);
obhod(p^.right);
end;
end;

Пока не додумаюсь никак, как реализовать удаление листа и при этом не удалить предыдущий узел, который после удаления листа сам может стать листом? (Думаю если только сначала обойти, запомнить какие узлы являются листьями и потом уже повторно обойти и удалить их)

Сообщение отредактировано: Account -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

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



Procedure DelTree(var p:tree);
Begin
if p<>nil then begin
DelTree(p^.Left);
DelTree(p^.Right);
Dispose(p);
p := nil;
end;
end;


Катит?

гы, 3 пробела отступ, оригинал.

Сообщение отредактировано: TarasBer -


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

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


Это удаляет полностью дерево, по поводу пробелов не догнал?

Сообщение отредактировано: Account -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата
Катит?
Сам-то как думаешь? Задание явно говорит:
Цитата
как реализовать удаление листа и при этом не удалить предыдущий узел, который после удаления листа сам может стать листом?
Твой код последовательно удаляет все листья до получения пустого дерева.

Account, вот чего я набросал:
function del_leaves(var p: ttree): boolean;
var
Lt, Rg: boolean;
begin
del_leaves := false;
if p = nil then exit;

del_leaves := true;
Rg := del_leaves(p^.right);
Lt := del_leaves(p^.left);

// только не надо умничать и вносить все вычисления вот в этот if,
// и избавляться от переменных Lt и Rg...
// Если я этого не сделал - значит, для этого были причины.
if not(Lt or Rg) then
begin
dispose(p);
p := nil;
end;
end;

Причин не работать не вижу, дерево создавать лениво, поэтому не проверял. Компиляцию вроде проходит.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

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


volvo, попробовал вроде все норм работает, но все равно еще сам попробую, а то как то нет желания чужое брать. На крайний случай если все же у самого не выйдет. А тебе очередное СПАСИБО! good.gif

Сообщение отредактировано: Account -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

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


volvo единственное баг, если дерево состоит из одного корня, то оно удаляется. Пока выявил только это).

Подправил этот баг вызовом функции из главной программы вот с таким условием:
if not (( t^.llink=nil) and (t^.rlink=nil)) then dellist(t);


Сообщение отредактировано: Account -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Цитата
если дерево состоит из одного корня, то оно удаляется.
Какой же это баг? Это правильное поведение: если в дереве только один корень - это лист. Где-то сказано, что корень не может быть листом? Нет. По определению лист - это узел, у которого нет потомков.
Цитата
Задание: Удалить все листья дерева.

Вот я его и удаляю. Что не так? Если тебе нужно было оставлять корень независимо от того, есть ли потомки - надо было говорить сразу, я бы сделал по-другому.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

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


volvo, ок. Значит не баг, но для себя подправил, чтоб если что препод не придирался)))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

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


я бы на месте препода наоборот придралась к "исправленному" поведению


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

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


мисс_граффити, посмотрим, придерется исправим обратно и все, деловто. По сути volvo прав на все 100%.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Бывалый
***

Группа: Пользователи
Сообщений: 212
Пол: Мужской

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


Всю ночь просидел но так своего алгоритма не придумал, видимо мозгов не хватает))))
Еще раз спасибо volvo.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





- Текстовая версия 22.10.2020 20:10
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name