Pull to refresh

Comments 29

Часто такое приходиться делать при выводе древовидных комментариев или каких либо категорий и под категорий постов на сайтах…
хм, и не подумал о таком применении, хотя очень логично :)
я на всех сайтах так структуру храню.
оч. удобно )
Спасибо! Как раз недавно проходил эту тему в университете и не до конца понял.
а где можно посмотреть 1-4 ??? — мне так понравилось!!! :)
google binary trees.
да и вообще чего тут сложного?
а вот скрестить это с nested sets уже интереснее ;)
ничего сложного :)
скрещивать незнаю, пока в планах осветить другие часто-используемые типы деревьев и некоторые другие структуры для эффективного хранения данных
Без простого не сделать сложного:)
Понятие «обход дерева» вы угадали :)
Ну и, наверное, на каждой «программерской» специальности в универе есть задача по описанию определенного вида дерева в виде связанного списка :)
:)
О да, мы имплементировали на яве простые деревья, двоичные, binary search trees и AVL-trees, и даже на финальном экзамене нужно было написать java-интерфейс для одной из таких структур
мне понравилось. хоть и слишком просто. даже для тех кто не проходил в институте)
у меня немного другое предложение. лучше программу всю составить. с необходимыми ссылками на источники информации. вот это было бы очень полезно.
Вы имеете ввиду прямо си- или ява-кодом? можно :)
Нет :) Не всмысле софта. Программа обучения. Тоесть вобщем выписать всю программу как содержание книжки.
Спасбио за лекцию. Было интересно как звучит по этому поводу теория… наверно многим программистам приходилось работать с деревьями на интуитивном уровне…

Подскажите плиз:
Есть ли какая-то теория по поводу сравнения двух узлов дерева.
Есть два узла и нужно определить какие положения они занимают в дереве относительно друг друга.
p1, p2. В варианте до которого додумал могут быть следующие ответы
p2==p1 — ответ 0,
p2 является одним из родителей p1 — ответ 1,
p2 не является одним из родителем то есть находится на каком-то отвороте с родителей p1 — ответ 2.
Таким образом compare(p1,p2) получим ответы -2,-1,0,1,2 и можно делать выводы и принимать решения.
Не хватает теории… может есть способ более детального описания положения точек друг относительно друга? Или как это относительное положение можно вообще описать
Смотря что вы считаете родителями и детьми. Например я могу начать обходить дерево с одного из этих узлов, а могу начать откуда-то со стороны. Поэтому для вашей задачи нужно использовать направленный граф, чтобы показывать кто кого породил. Однако и в таком случае может получиться так, что два узла не являются родительскими по отношению друг к другу, простой пример: p1 -> pX < — p2.
Так понял вы говорить про какой-то более общий случай.
В случае, вроде файловой системы, у узла один родитель, и два узла быть родителями друг друга в принципе не могут… По моему, дерево уже подразумевает что родитель у узла только один, и как следствие у дерева один корень.
Вообще я теорию не знаю, потому и спрашиваю, как можно описать положение двух узлов относительно друг друга… пошёл смотреть, что такое направленный граф
Вы про фс не упоминали, так что уж извините. Направленный граф это когда вы между двумя узлами ставите не линию, а стрелочку, обозначая кто из них родитель.
Вбиваю в google «направленый граф» первая в списке ссылка с описанием
«Направленный граф то же что Ориентированный граф.»
ништяк)
В файловой системе узлы друг относительно друга описываются относительными ссылками, Тоже вариант иди наверх, наверх, потом сюда туда и я тут.
Ну, если взять легкий вариант с бинарным деревом, где, как кто-то ниже уже указал, у узла не может быть двух родителей «первого уровня».
обычно такие деревья делаются через двойные связные списки, то есть простой проверкой p1.parent==p2 или p2.leftChild==p1 можно определить эту свзяь

если же интересует является ли узел p1 хоть каким-нибудь родителем узла p2 (то есть, если двигаться от узла p1 только вниз, можно ли добраться до узла p2), то алгоритм тоже получается простой (while iterator.next!=p2 бла бла), но в плане эффективности будет уже намного медленнее первого (O(logn))
Уважаемый freetonik.
Нескромный вопрос — а вот презентации powerpoint-овские по которой рассказываете можете выложить?
Конечно :)
https://dl.getdropbox.com/u/72746/css/comp%202402/trees/Trees.ppt
«Свойства двоичных деревьев» при данном определении не работают: или в определении потомков должно быть либо нуль либо два; или в свойствах — количества узлов соотносятся как неравенства.
Спасибо за информацию, но мне кажется много лишних слов в видео.
Я чего-то недопонял или на 12-ом слайде ошибка?

Судя по алгоритму, узел посещается после посещения его левого и до посещения правого поддерева. В слайде же написано, что «узел посещается после посещения его левого и правого поддерева»…

Это описание прямо столку сбило )
Only those users with full accounts are able to leave comments. Log in, please.