Алгоритм поиска по дереву мы рассмотрели выше. Функция поиска .
Обход в глубину «сверху вниз»: название имеет смысл лишь в случае стандартного расположения дерева корнем кверху. Алгоритм обхода Начать с корня дерева. Пометить текущую вершину. Совершить прямой обход левого поддерева. Совершить прямой обход правого поддерева. Пример Пример Рассмотрим пример всех способов обхода дерева, изображенного на рисунке:
Порядок узлов данного дерева в случае прямого обхода будет следующим: 1 2 3 5 8 9 6 10 4 7. Обратный обход этого же дерева даст нам следующий порядок узлов: 2 8 9 5 10 6 3 7 4 1. При симметричном обходе мы получим следующую последовательность узлов: 2 1 8 5 9 3 10 6 7 4.
|
