Удаление всех листьев дерева
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется .
2. Все тексты программ должны помещаться в теги [code=pas] . [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. «FAQ«, если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение — только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы — на PM!
6. Одна тема — один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме.
8. Спрашивайте и отвечайте четко и по существу.
Группа: Пользователи
Сообщений: 212
Пол: Мужской
Есть задача. Имеется бинарное дерево. Информация в узлах не важна (могут быть цифры, могут быть буквы).
Задание: Удалить все листья дерева.
Procedure obhod(p:tree);
Begin
if p<>nil then
begin
obhod(p^.left);
writeln(p^.inf);
obhod(p^.right);
end;
end;
Пока не додумаюсь никак, как реализовать удаление листа и при этом не удалить предыдущий узел, который после удаления листа сам может стать листом? (Думаю если только сначала обойти, запомнить какие узлы являются листьями и потом уже повторно обойти и удалить их)
Сообщение отредактировано: Account — 14.10.2010 3:26
Группа: Пользователи
Сообщений: 1 755
Пол: Мужской
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 — 14.10.2010 3:34
Источник
Удаление всех листьев дерева
Название темы должно быть информативным !
Прежде чем задать вопрос, воспользуйтесь Поиском . и проверьте в FAQ (ЧАВО) Паскаля
Чтобы получить вразумительный ответ, подробно опишите проблему: что надо сделать, что не получается и номер ошибки (если есть), которую выводит компилятор. Для вставки кода ваших программ используйте, пожалуйста, кнопку СODE=pas или выпадающий список СODE для других языков (подсветка синтаксиса). [!] Как правильно задавать вопросы | Руководство по языку B.Pascal 7 & Objects/LR | Borland Pascal. Руководство пользователя
Всем программистам привет! Respect!
Работаю с бинарными деревьями. Подскажите плиз как правильно реализовать процедуру удаления всех листьев дерева. Давно мучаюсь, никак не получается, вроде понимаю, но все равно выводит не то что нужно..
вот мои исходник:
так описывается динамическая структура:
также имеется процедура remove, позволяющая удалить узел дерева, но все равно не получается.
подскажите как быть то?? буду очень признателен.
Добавлено 27.05.09, 00:38
с огромным трудом и методом перебора различных вариации (почти тыком) поборол данную проблему следующим кодом:
одну процедуру так и не смог реализовать до конца: удалить заданныи узел, а также всех его потомков (как слева, так и справа). т е все поддеревья.
думал, что используя функцию find получу указатель на заданныи элемент и затем воспользуюсь процедурои удаления всего дерева, но передав не указатель на корень, а указатель на искомыи узел. ведь бинарное дерево — структура рекурсивная и каждыи узел можно рассматривать как корневои. Но ничего не вышло, не удалял вообще вроде.
в итоге реализовал, но работает ужасно не стабильно и выполняем немного не те деиствия. Происходит удаление все потомков искомого узла, но удаление его самого не происходит, также при повторном удалении этого элемента со всеми поддеревьями происходит разименование не существующего указателя.
структура TptrElem описана в первом посте..
никак не получается понять как обрабатывать бинарные деревья..где использовать var, а где не нужно.
когда стоит var у формальнои статическои переменнои, это значит, что передается не копия объекта, а его адрес, поэтому меняя значение этои переменнои внутри подпрограммы, будет изменен и соот — щии фактически параметр.
а если передается var указатель, то в этом случае передается адрес куда он указывает или адрес самого указателя. и что передается к формальному параметру, если var у указателя не поставить.
подскажите как быть то. буду очень признателен.
Удаление поддерева, на которое указывает P, должно произойти при вот таком вот вызове:
(DeleteMin и Remove лежат у меня на сайте)
Времени тестировать нет, попробуй, вроде нигде не ошибся, должно работать. Если что не ясно — спрашивай, я буду чуть позже, расскажу подробнее.
спасибо огромнеишее, все получилось теперь. как вам так удается понимать так быстро такие в моем понимании сложнеишие вещи.
саму процедуру не понял до конца..
вообще деревья не понимаю фундаментально, поверхностно может быть..да и то, недовлен уровнем понимания.
для меня это вообще номер один было, когда разрабатывал модуль для работы с деревьями..я ваш модуль проштудировал вдоль и поперек, использовал наверное вообще все функции, которые вы привели . пасибо! очень помог. очень. А не хотите увеличить подпрограмм для обработки бинарных деревьев. ведь их можно придумать сотню наверное точно.
работает КАК ВСЕГДА идеально.
подскажите плиз как проводить изучение бинарных деревьев, потому что я их не понимаю фундаментально. точнее я понимаю прекрасно как описывается элемент узла с точки зрения Паскаля, но не понимаю на чем фундаметально строятся подпрограммы обработки деревьев. на рекурсии в основном, но почему в некоторых случаях параметры как var, а иногда не как var..вроде понимаю за что отвечает var, а все равно не понятно до конца. А здесь если хоть в одном месте допустил неточность — крах.
P.S. видел примеры программ СИЛЬНОВЕТВЯЩИХСЯ ДЕРЕВЬЕВ..чуть плохо не стало, такое вообще невозможно понять ведь. а ведь имеются гуру, разбирающиеся в них и довольно неплохо.
Чтобы удалить узел и всех его потомков — недостаточно сделать то, что было сделано в первых двух постах. То есть, даже если все правильно удалится (сам узел и его левое/правое поддеревья), то будет проблема с предком того узла, на который указывает P. Он будет указывать в «пустоту», естественно, при попытке распечатать содержимое будет мусор (в худшем случае — вылет по разыменованию nil).
Что делать? А ничего не делать. Не строить велосипедов, самое главное Все просто: Обходим (рекурсивно) удаляемое «дерево», при этом locRoot указывает на всех потомков заданного для удаления узла. Когда рекурсия начнет раскручиваться назад, просто удаляем из дерева (Root — глобальный корень, заметь) элементы со значениями locRoot^.inf1, поскольку в процедуру удаления передается именно корень дерева, то все действия, описанные в комментариях к процедуре Remove выполняются правильно, и все ссылки на удаляемые узлы корректируются как положено. Вот и все, собственно.
почему в некоторых случаях параметры как var, а иногда не как var..вроде понимаю за что отвечает var, а все равно не понятно до конца
Что непонятного? Если не хочешь, чтобы изменения параметра передавались в вызывающую программу — Var не используй. Хочешь видеть в вызывающей программе измененное подпрограммой значение — используй. Вот тебе пример:
Ну, и чего ты добьешься? Память освобождена, но p не присвоилось значение nil, значит, условие выполнится, и опять будет распечатан мусор. Значит, надо использовать Var. Запомни, что если ты передаешь указатель — неважно, как ты его передашь, значение, на которое он указывает можно изменить. А вот можно ли изменить сам указатель, и будет ли это изменение передано назад — это зависит от наличия спецификатора var или const, или их отсутствия.
А не хотите увеличить подпрограмм для обработки бинарных деревьев. ведь их можно придумать сотню наверное точно?
Ну, пока выясняется, что при наличии только того, что есть на сайте, можно решать и совершенно постороннюю задачу Зачем же плодить подпрограммы?
видел примеры программ СИЛЬНОВЕТВЯЩИХСЯ ДЕРЕВЬЕВ..чуть плохо не стало, такое вообще невозможно понять ведь
Точно так же, как разберешься с бинарными деревьями — разберешься и с сильноветвящимися, когда приспичит
Чтобы удалить узел и всех его потомков — недостаточно сделать то, что было сделано в первых двух постах. То есть, даже если все правильно удалится (сам узел и его левое/правое поддеревья), то будет проблема с предком того узла, на который указывает P. Он будет указывать в «пустоту», естественно, при попытке распечатать содержимое будет мусор (в худшем случае — вылет по разыменованию nil).
вот это понял очень хорошо.
знал, что удалить мало и нужно либо таскать с собои еще один указатель, опоздывающии на один шаг (но реализовать бы все равно не смог) или как то еще. вы привели процедуру
в которои все прекрасно отслеживается..вроде понимал это, но реализовать бы без вашеи помощи точно бы не смог.
передаешь указатель — неважно, как ты его передашь, значение, на которое он указывает можно изменить. А вот можно ли изменить сам указатель, и будет ли это изменение передано назад — это зависит от наличия спецификатора var или const, или их отсутствия.
если указатель var, если меняю указатель (смещаю по памяти) то смещается и указатель — фактическии параметр.
если указатель const, тогда смещение недопустимо(константныи указатель на неконстантные данные), но данные на которые указывает указатель изменны.
если указатель как не var и не const, то создается копия указателя (т е выделяется память под сам указатель, т к он тоже переменная и ему тоже нужна память), но указывает он туда же, куда и указатель — фактическии параметр. Т е разделюят одну и ту же область памяти. Если меняю значение, то меняется для всех, а если сдвигаю, то фактическии указатель не меняет своего положения.
вот это понимаю все, но все усложняется еще рекурсиеи.
Память освобождена, но p не присвоилось значение nil, значит, условие выполнится, и опять будет распечатан мусор. Значит, надо использовать Var.
пасибо большое за пояснение.
Без вас бы не справился.
P.S. вообще тема сложная имхо. если брать списки, то они легче в несколько раз для понимания.
Источник
Удаление листьев из дерева
Ситуация такая: Дано вот такое несовсем понятное задание, но оно описано именно так, как я и выкладываю.
Дан код дерева, нужно закончить его редактировать, т.е. закончить удаление листка (только того значения, оставляя те листья, которые были внутри того листка).
Честно говоря, не понимаю задания, что конкретно нужно сделать? Я в Java не силён, а потому несовсем представляю, как можно реализовать удаление.
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
package derevo; public class List { int znacenije; List left; List right; List roditel; public List(int l, List t) { znacenije = l; roditel = t; } public void dobavitList(int sk, List t) { if (sk > znacenije) { if (right != null) { right.dobavitList(sk, this.right); } else { right = new List(sk, t); } } else if (sk znacenije) { if (left != null) { left.dobavitList(sk, this.left); } else { left = new List(sk, t); } } } public void printList(String tabas) { if (left != null) { left.printList(tabas + "\t"); } System.out.println(tabas + " " + this.znacenije+" - "+((roditel!=null)?roditel.znacenije:0)); if (right != null) { right.printList(tabas + "\t"); } } public List find(int sk) { if (this.znacenije == sk) { return this; } else { if (sk > this.znacenije && right != null) { return right.find(sk); } else if (sk this.znacenije && left != null) { return left.find(sk); } } return null; } @Override public String toString() { return "List + "znacenije=" + znacenije+" "+roditel.znacenije + '>'; } }
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
package derevo; public class Derevce { List verhushka; public void dobavitList(int sk) { if (verhushka != null) { verhushka.dobavitList(sk, verhushka); } else { verhushka = new List(sk, null); } } public void udalitList(int sk) { List sl = findList(sk); if (sl.right == null && sl.right == null) { if (sk > sl.roditel.znacenije) { sl.roditel.right = null; } else if (sk sl.roditel.znacenije) { sl.roditel.left = null; } } /*Здесь ещё нужно добавить код, который бы удалял и те листья, у которых есть подлистья (т.е. правую, левую либо обе ветки) */ } public List findList(int sk) { if (verhushka != null) { return verhushka.find(sk); } return null; } public void pechatat() { if (verhushka != null) { verhushka.printList(""); } else { System.out.println("Derevo pustoje"); } } }
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
package derevo; public class PrimerDereva { public static void main(String[] args) { Derevce m = new Derevce(); //m.spausdinti(); m.dobavitList(4); m.dobavitList(2); m.dobavitList(3); m.dobavitList(1); m.dobavitList(6); m.dobavitList(9); m.dobavitList(19); m.pechatat(); m.udalitList(19); m.pechatat(); m.udalitList(2); m.pechatat(); List a = m.findList(23); System.out.println(a); } }
Источник