Поиск всех элементов, как?

Question

[nvdfxx]

Есть родительский элемент, у него может быть сколько угодно дочерних, у этих дочерних тоже может быть сколько угодно дочерних и т.д. Как пройти по всем элементам и записать в массив? ЯП не важен, хоть псевдокод. Рекурсивно или нет, тоже разницы нет, какой самый быстрый алгоритм?

Comments

[Roman]

у него может быть сколько угодно дочерних, у этих дочерних тоже может быть сколько угодно дочерних и т.д.

Рекурсивно или нет, тоже разницы нет

стек отвалится.

Answer 1

[longclaps]

Senior Pomidor developer

#!/bin/pomidor

функцыя всехпорву(аргумент, мешок){
    мешок.запихнуть(аргумент)
    длявсех(детей аргумента){
        всехпорву(детей, мешок)
    }
}

конкретный_мешок = []
всехпорву(конкретный_аргумент, конкретный_мешок)

Comments

[nvdfxx]

Это самый быстрый алгоритм?

[longclaps]

nvdfxx, дорогой! Можно попробовать написать и побыстрее - главное решить, какие строки выкинуть. Но я уже стар, чтобы гоняться взапуски - поэкспериментируй сам.

Answer 2

[EVGENY T.]

Рекурсия проще всего:

процедура_печать_дерева(узел) {
печать(узел)
для всех дочерей {
процедура_печать_дерева(дочерний узел) }
}

Comments

[nvdfxx]

Это самый быстрый алгоритм?

[EVGENY T.]

nvdfxx, ну смотри тут выходит у нас O(n). Как можно обойти дерево из n элементов быстрее, чем за n шагов? Никак.

Answer 3

[dmshar]

Вопрос к Senior Pomidor developer - а синьор хоть понимает, что это будут разные алгоритмы в зависимости от того, что у вас в основе - дерево, направленный граф, или вообще - ненаправленный граф? Если понимает, то почему не указал явно? Если нет - тогда зачем ему этот алгоритм? Да и алгоритм вообще?

Comments

[nvdfxx]

Можете представить как экземпляр класса Item, у которого есть поле childrens, в котором экземпляры класса Item, у которых есть поле childrens

[Roman]

nvdfxx, https://learnc.info/adt/binary_tree_traversal.html

Если дерево растёт бесконечно в глубину, то его можно обрабатывать, используя проход в ширину. То есть, известно, что если спускаться вниз по ветви, то до конца мы не дойдём, но на данном уровне дерево имеет конечный размер.

Если дерево растёт бесконечно в ширину, но при этом имеет конечную глубину (то есть, у узла не два наследника, а из бесконечно много), то можно использовать поиск в глубину.

[dmshar]

Roman, Ну, после этого ответа тему можно закрывать - добавить нечего. Имеется всего два алгоритма, примерно равные по сложности в общем случае. Выбор конкретного варианта зависит от факторов, лежащих вне математико-логических построений - т.е. от знаний того, какой приоритетный способ наращивания дерева.

[nvdfxx]

Roman, эти варианты разве не только для бинарных деревьев подходят?

[Владимир Олохтонов]

nvdfxx, для обоих алгоритмов единственное требование — возможность упорядочить детей у вершины.

[dmshar]

nvdfxx, Где вы взяли информацию про ограничение в виде требований бинарности деревьев?

Владимир Олохтонов, мне кажется, требование упорядочения слишком жесткое. Достаточно требования перечислимости всех потомков.

[Владимир Олохтонов]

dmshar, тогда не очень понятно как определить обход в ширину :) если при каждом новом вызове мы будем получать новый порядок потомков, то мы не сможем выписать порядок обхода. Впрочем для многих задач это и не требуется :)

[nvdfxx]

dmshar, Владимир Олохтонов, спасибо