Алгоритми обходу бінарного дерева пошуку

Як і будь-яке дерево, бінарне дерево пошуку можна обходити у префіксному, інфіксному та постфіксному порядку. Обхід бінарного дерева пошуку у інфіксном порядку завжди оброблятиме вузли у зростаючому порядку.

Функції, що здійснюють обхід дерева, приймають один аргумент – вказівник на вершину дерева. Причому ці функції. Як і функція вставки вузла є рекурсивними. Наприклад функція інфіксного обходу дерева, написана на мові (С++), може виглядати наступним чином:

void inOrder (TREENODEPTR treePtr) {

inOrder (treePtr -> lPtr);

cout << (treePtr -> data);

inOrder (treePtr -> rPtr);

}

Для префіксного та постфіксного обходу мінятиметься лише послідовність виконання операторів, що складають тіло функції.