Есть много способов обойти бинарное дерево. Двумя наиболее распространенными способами обхода бинарного дерева являются поиск в глубину и поиск в ширину.
Поиск в глубину
Поиск в глубину работает, начиная с корневого узла и проходя как можно дальше по ветвям дерева. Как только поиск достигает конца ветки, он рекурсивно возвращается и начинает поиск в следующей ветке. Существует три типа обхода, которые использует поиск в глубину.
Обход по порядку выполняется в порядке левый-коренной-правый.
Пример распечатки чисел дерева
Вы начинаете с 12, потому что это корневой узел для этого дерева. 12 — это корневой узел, поэтому вы перейдете к левому узлу, который равен 10.
10 два дочерних элемента, поэтому вы продолжите переход к левому дочернему элементу 9.
Число 9 не имеет потомков, поэтому оно будет напечатано первым. Затем вы вернетесь к 10.
Теперь мы напечатаем 10, потому что это родитель узлов 9 и 11. Затем вы пойдете в 11.
11 не имеет дочерних элементов и является правильным узлом для 10, поэтому он будет напечатан следующим. Теперь вернитесь к 12, потому что все узлы слева от 12 напечатаны.
Теперь вы напечатаете корневой узел 12 и перейдете к правому узлу, который равен 14.
У 14 двое детей, поэтому вы пойдете налево до 13.
13 не имеет детей, поэтому он будет напечатан. Затем вы вернетесь к 14.
Теперь вы напечатаете 14, потому что это родитель 13. Затем вы перейдете сразу к 15.
15 не имеет дочерних элементов, поэтому вы напечатаете 15. Это последний шаг, так как все узлы были напечатаны.
Следующий тип обхода — обход предварительного порядка. Предзаказ осуществляется в порядке корень-левый-правый. Шаги аналогичны порядку, за исключением того, что сначала вы печатаете корень, затем левый и, наконец, правый. Для предыдущего дерева выход обхода дерева предварительного порядка будет 12, 10, 9, 11, 14, 13, 15.
Последний тип — обход в обратном порядке. Почтовый порядок в порядке левый-правый-корень. Вы напечатаете левые узлы, затем правые узлы и, наконец, корневые узлы. Для предыдущего дерева выход обхода дерева в обратном порядке будет 9, 11, 10, 13, 15, 14, 12.
Поиск в ширину
Поиск в ширину — это метод обхода, который использует очередь для хранения значений всех узлов на текущем уровне перед переходом на уровень ниже.
Пример
Начиная с корня, мы добавляем 12 в очередь.
Теперь вы напечатаете 12 и перейдете к детям 12. Вы добавите 10 и 14 в очередь.
Теперь выведите 10 и добавьте в очередь всех потомков 10.
Теперь мы печатаем 14 и добавляем в очередь дочерние элементы 14.
Теперь вы продолжите этот шаблон, выводя число в начало очереди и добавляя его дочерние элементы в конец очереди. В этом случае дочерних узлов больше нет, поэтому вы будете печатать очередь, пока она не станет пустой. Вы знаете, что закончили, когда очередь пуста и больше не осталось детей.
