Симметричный метод прохождения начинает свои действия в узле спуском по его левому поддереву. Затем выполняется второе действие - обработка данных в узле. Третье действие - рекурсивное прохождение правого поддерева. В процессе рекурсивного спуска действия алгоритма повторяются в каждом новом узле.
Итак, порядок операций при симметричном методе следующий:
1) прохождение левого поддерева.
2) посещение узла.
3) прохождение правого поддерева.
Мы называем такое прохождение LNR (left, node, right).
При симметричном методе прохождения дерева Tree_0 выполняются следующие операции.
| Действие
| Прохождение
| Замечания
|
| Спуститься от A к B:
|
| Левый сын узла B равен NULL
|
| Посетить B;
| B
|
|
| Спуститься от B к D:
|
| D -листовой узел
|
| Посетить D;
| D
| Конец левого поддерева узла A
|
| Посетить корень A:
| A
|
|
| Спуститься от A к C:
|
|
|
| Спуститься от C к E:
|
| E - листовой узел
|
| Посетить E;
| E
|
|
| Посетить C;
| C
| Готово!
|
Узлы посещаются в порядке B D A E C. Рекурсивная функция сначала спускается по левому дереву [t ->Left()], а затем посещает узел. Второй шаг рекурсии спускается по правому дереву [t ->Right()].
// Симметричное рекурсивное прохождение узлов дерева
template <class T>
void Inorder (TreeNode<T> *t, void visit(T& item))
{
//Рекурсивное прохождение завершается на пустом поддереве
if (t != NULL)
{
//Спуститься по левому поддереву
Inorder(t->Left(), visit);
//Посетить узел
visit(t->data);
//Спуститься по правому поддереву
Inorder(t->Right(), visit);
}
}
