Обход — это процесс, который посещает все узлы дерева и может также печатать их значения. Поскольку все узлы связаны через ребра (ссылки), мы всегда начинаем с корневого (головного) узла. То есть мы не можем получить произвольный доступ к узлу в дереве. Есть три способа прохождения дерева:
- Порядок обхода
- Предварительный заказ обхода
- Обход после заказа
Как правило, мы пересекаем дерево, чтобы найти или найти данный элемент или ключ в дереве или распечатать все содержащиеся в нем значения.
Порядок обхода
В этом методе обхода сначала посещается левое поддерево, затем корень, а затем правое поддерево. Мы всегда должны помнить, что каждый узел может представлять само поддерево.
Если двоичное дерево просматривается по порядку , выходные данные будут генерировать отсортированные значения ключа в порядке возрастания.
Мы начинаем с A и, следуя по порядку, переходим к его левому поддереву B. B также пройден по порядку. Процесс продолжается до тех пор, пока не будут посещены все узлы. Вывод обхода этого дерева по порядку будет —
D → B → E → A → F → C → G
Алгоритм
Until all nodes are traversed − Step 1 − Recursively traverse left subtree. Step 2 − Visit root node. Step 3 − Recursively traverse right subtree.
Предварительный заказ обхода
В этом методе обхода сначала посещается корневой узел, затем левое поддерево и, наконец, правое поддерево.
Мы начинаем с A и, следуя предварительному заказу, сначала посещаем саму A , а затем перемещаемся в его левое поддерево B. B также пройден предварительный заказ. Процесс продолжается до тех пор, пока не будут посещены все узлы. Вывод обхода предзаказа этого дерева будет —
A → B → D → E → C → F → G
Алгоритм
Until all nodes are traversed − Step 1 − Visit root node. Step 2 − Recursively traverse left subtree. Step 3 − Recursively traverse right subtree.
Обход после заказа
В этом методе обхода корневой узел посещается последним, отсюда и имя. Сначала мы пересекаем левое поддерево, затем правое поддерево и, наконец, корневой узел.
Мы начинаем с A , и после прохождения Post-order мы сначала посещаем левое поддерево B. B также пройден после заказа. Процесс продолжается до тех пор, пока не будут посещены все узлы. Результат пост-обхода этого дерева будет —
D → E → B → F → G → C → A
Алгоритм
Until all nodes are traversed − Step 1 − Recursively traverse left subtree. Step 2 − Recursively traverse right subtree. Step 3 − Visit root node.
Чтобы проверить реализацию обхода дерева в C, нажмите здесь .