• Применим ли симметричный обход для не бинарных деревьев?

    @res2001
    Developer, ex-admin
    Просто размышление.
    Логика подсказывает, что такой подход применяется, когда нужно не просто обойти все дерево как-нибудь, а обойти в порядке сортировки дерева (или в обратном порядке).

    Конечно вы можете применять такое и с деревьями с большим количеством узлов. Но это будет уже, скорее всего, не симметричный обход, потому что симметрей чисто визуально тут уже и не пахнет, но алгоритмическе все то же самое. В некоторых конфигурациях деревьев с количеством дочерних узлов больше 2, обход вполне может остаться симметричным (когда дочерних узлов четное количество и родителя проверяете по середине).

    На каком именно этапе проверять родителя в таком случае зависит от того как сортируются потомки относительно родителя в данном конкретном случае. Т.е. в бинарном дереве левый потомок меньше родителя, а правый больше - это правило и создает упорядоченность при обходе. Если узлов больше 2, то нужно определить аналогичное правило упорядоченности для потомков относительно родителя. в соответствии с этим правилом и совершать обход.
    Ответ написан
    1 комментарий