@toNtr

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

Всем привет!
Начал изучать алгоритмы обхода деревьев и заметил что во всех примерах симметричный обход применяется только к бинарным деревьям, но не смог найти где прямо говорилось бы, что другие виды деревьев так обойти нельзя или примеры их обхода.

При симметричном обходе бинарного дерева мы проверяем сначала одного потомка, затем родителя, затем другого потомка. Но если предположить что потомков больше двух, то появляется вопрос: в после какого потомка проверять родителя или родитель проверяется после каждого потомка, кроме последнего?

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы