Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Индекс 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
Ключ 
8 7 9 3 11 2 5 10 15 1 4 6 13 19 12 14 
Левый 
2 4 0 6 8 10 11 0 13 0 0 0 15 0 0 0 
Правый 
3 0 5 7 9 0 12 0 14 0 0 0 16 0 0 0 
В связи с двоичными деревьями (и деревьями вообще) вводится важная 
категория алгоритмов: алгоритмы обхода дерева. Такой алгоритм – это ме-
тод, который позволяет получить доступ к каждому узлу дерева один и толь-
ко один раз.
Для каждого узла выполняются некоторые виды обработки (проверка, 
суммирование и т.п.), однако способ обхода не зависит от конкретных дейст-
вий и является общим для всех алгоритмов обработки узлов.
Отдельные узлы посещаются в некотором определенном порядке. Су-
ществуют три порядка, использующие обход в глубину: 
1. Сверху-вниз (PreOrder):
− обработать корень; 
− обход левого поддерева; 
− обход правого поддерева; 
2. Слева-направо (InOrder): 
− обход левого поддерева; 
− обработать корень; 
− обход правого поддерева; 
3. Снизу-вверх (PostOrder): 
− обход левого поддерева; 
− обход правого поддерева; 
− обработать корень. 
Четвертый порядок обхода узлов дерева можно назвать обходом в ши-
рину. В этом случае сначала обращаются ко всем узлам на данном уровне 
дерева, а затем переходят к следующему уровню. Обход в ширину часто ис-
пользуется в алгоритмах, осуществляющий полный поиск в дереве. Наиболее 
9 / 23

---

79 
прост алгоритм обхода в ширину при представлении дерева в виде массива – 
это цикл по всем элементам. 
Для дерева, представленного на рисунке 4.1, четыре способа обхода
дают следующий результат: 
1) 8 7 3 2 1 5 4 6 9 11 10 15 13 12 14 19 
2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 19 
3) 1 2 4 6 5 3 7 10 12 14 13 19 15 11 9 8 
4) 8 7 9 3 11 2 5 10 15 1 4 6 13 19 12 14 
Первые три метода легко представить в виде рекурсивных процедур. 
Процедуры просты, и это свидетельство того, что рекурсивные структуры 
естественнее всего описывать рекурсивными алгоритмами. 
Процедуры представлены в листинге 4.3. Функция Proc выполняет не-
которые действия для конкретного узла. Учитывается приведенное выше 
описание узла дерева.