окрема існує три способи: можна проходити вузли в прямому, зворотному і кінцевому порядку. p align="justify"> Алгоритм обходу в прямому порядку:
Потрапити в корінь,
Пройти всі поддеревья зліва на право в прямому порядку.
Даний алгоритм рекурсівен, так як проходження дерева містить проходження піддерев, а вони в свою чергу проходяться по тому ж алгоритму.
Зокрема для дерева на рис. 3 і 4 прямий обхід дає послідовність вузлів: A, B, C, D, E, G, H.
Получающаяся послідовність відповідає послідовному зліва направо перерахуванню вузлів при поданні дерева за допомогою вкладених дужок і в десятковій системі Дьюї, а також проходу зверху вниз при поданні у вигляді уступчатого списку.
При реалізації цього алгоритму мовою програмування потрапляння в корінь відповідає виконання процедурою або функцією деяких дій, а проходження піддерев - рекурсивним викликам самої себе. Зокрема для бінарного дерева (де з кожного вузла виходить не більше двох піддерев) відповідна процедура буде виглядати так:
// Preorder Traversal - англійська назва для прямого порядку
procedure PreorderTraversal ({Аргументи});
// Проходження кореня
DoSomething ({Аргументи});
// Проходження лівого піддерева {Існує ліве піддерево} then ({Аргументи 2});
// Проходження правого піддерева {Існує праве піддерево} then ({Аргументи 3});;
Тобто спочатку процедура виробляє всі дії, а тільки потім відбуваються всі рекурсивні виклики.
Алгоритм обходу в зворотному порядку:
Пройти ліве піддерево,
Потрапити в корінь,
Пройти наступне за лівим піддерево.
Потрапити в корінь,
і т.д поки не буде пройдено крайнє праве піддерево.
Тобто проходяться всі поддеревья зліва на право, а повернення в корінь розташовується між цими проходженнями. Для дерева на рис. 3 і 4 це дає послідовність вузлів: B, A, D, C, E, G, F.
У відповідній рекурсивної процедурою дії будуть розташовуватися в проміжках між рекурсивними викликами. Зокрема для бінарного дерева:
// Inorder Traversal - англійська назва для зворотного порядкаInorderTraversal ({Аргументи});
// Проходження лівого піддерева {Існує ліве піддерево} then ({Аргументи 2});
// Проходження кореня ({Аргументи});
// Проходження правого піддерева {Існує праве піддерево} then ({Аргументи 3});;
Алгоритм обходу в кінцевому порядку:
Пройти всі поддеревья зліва на право,
Потрапити...
