Эйлеров обход
Материал из Algocode wiki
Версия от 10:06, 27 ноября 2019; Глеб (обсуждение | вклад)
Определение
Эйлеров обход -- способ представить подвешенное неориентированное дерево массивом чисел. Существуют несколько способов построить такой обход и каждый вариант обход имеет свои плюсы и минусы.
Варианты
1) Давайте выпишем все рёбра дерева (ориентированные) в порядке DFS'а. Именно такой подход описан на википедии
2) Каждая вершина добавляется в массив дважды: когда мы в неё заходим и когда выходим(то есть когда ставим tin, tout). Каждому листу соответствует два последовательных вхождения(кроме может быть одной вершины, подумайте какой).
3) Каждая вершина добавляется в массив всякий раз, когда мы её посещаем (когда спускаемся из предка и поднимаемся из потомка).
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin