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