На этом шаге мы рассмотрим алгоритм обратного обхода бинарного дерева.
И, наконец, приведем алгорим обратного обхода дерева, который заключается в следующем:
- обойдите левое поддерево;
- посетите корень дерева;
- обойдите правое поддерево.
Применяя этот алгоритм к бинарным деревьям I, II, обойдем вершины в следующем порядке:
Рис.1. Примеры бинарных деревьев
происходит в следующем порядке:
M D N B E A C
D B E C R
Запишем алгоритм в виде рекурсивной функции:
void ObhodBack (node **w) // Обратный обход бинарного дерева. // *w - указатель на корень дерева. { if (*w!=NULL) { ObhodBack (&((**w).Left)); cout<<(**w).Key<<" "; ObhodBack (&((**w).Right)); } }
На следующем шаге мы приведем алгоритм вывода бинарного дерева.
