Комментарии 29
Часто такое приходиться делать при выводе древовидных комментариев или каких либо категорий и под категорий постов на сайтах…
Спасибо! Как раз недавно проходил эту тему в университете и не до конца понял.
google binary trees.
да и вообще чего тут сложного?
а вот скрестить это с nested sets уже интереснее ;)
да и вообще чего тут сложного?
а вот скрестить это с nested sets уже интереснее ;)
Понятие «обход дерева» вы угадали :)
Ну и, наверное, на каждой «программерской» специальности в универе есть задача по описанию определенного вида дерева в виде связанного списка :)
Ну и, наверное, на каждой «программерской» специальности в универе есть задача по описанию определенного вида дерева в виде связанного списка :)
мне понравилось. хоть и слишком просто. даже для тех кто не проходил в институте)
у меня немного другое предложение. лучше программу всю составить. с необходимыми ссылками на источники информации. вот это было бы очень полезно.
у меня немного другое предложение. лучше программу всю составить. с необходимыми ссылками на источники информации. вот это было бы очень полезно.
Спасбио за лекцию. Было интересно как звучит по этому поводу теория… наверно многим программистам приходилось работать с деревьями на интуитивном уровне…
Подскажите плиз:
Есть ли какая-то теория по поводу сравнения двух узлов дерева.
Есть два узла и нужно определить какие положения они занимают в дереве относительно друг друга.
p1, p2. В варианте до которого додумал могут быть следующие ответы
p2==p1 — ответ 0,
p2 является одним из родителей p1 — ответ 1,
p2 не является одним из родителем то есть находится на каком-то отвороте с родителей p1 — ответ 2.
Таким образом compare(p1,p2) получим ответы -2,-1,0,1,2 и можно делать выводы и принимать решения.
Не хватает теории… может есть способ более детального описания положения точек друг относительно друга? Или как это относительное положение можно вообще описать
Подскажите плиз:
Есть ли какая-то теория по поводу сравнения двух узлов дерева.
Есть два узла и нужно определить какие положения они занимают в дереве относительно друг друга.
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))
обычно такие деревья делаются через двойные связные списки, то есть простой проверкой p1.parent==p2 или p2.leftChild==p1 можно определить эту свзяь
если же интересует является ли узел p1 хоть каким-нибудь родителем узла p2 (то есть, если двигаться от узла p1 только вниз, можно ли добраться до узла p2), то алгоритм тоже получается простой (while iterator.next!=p2 бла бла), но в плане эффективности будет уже намного медленнее первого (O(logn))
Уважаемый freetonik.
Нескромный вопрос — а вот презентации powerpoint-овские по которой рассказываете можете выложить?
Нескромный вопрос — а вот презентации powerpoint-овские по которой рассказываете можете выложить?
«Свойства двоичных деревьев» при данном определении не работают: или в определении потомков должно быть либо нуль либо два; или в свойствах — количества узлов соотносятся как неравенства.
Спасибо за информацию, но мне кажется много лишних слов в видео.
согласен, не особо. досматривать не стал.
Я чего-то недопонял или на 12-ом слайде ошибка?
Судя по алгоритму, узел посещается после посещения его левого и до посещения правого поддерева. В слайде же написано, что «узел посещается после посещения его левого и правого поддерева»…
Это описание прямо столку сбило )
Судя по алгоритму, узел посещается после посещения его левого и до посещения правого поддерева. В слайде же написано, что «узел посещается после посещения его левого и правого поддерева»…
Это описание прямо столку сбило )
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Деревья, двоичные деревья