Структура данных и алгоритмы - обход дерева

Обход - это процесс посещения всех узлов дерева и также может распечатать их значения. Поскольку все узлы соединены ребрами (связями), мы всегда начинаем с корневого (головного) узла. То есть мы не можем получить произвольный доступ к узлу в дереве. Есть три способа, которые мы используем, чтобы пройти по дереву:

• Обход по порядку
• Предварительный заказ обхода
• Пост-заказ обход

Обычно мы перемещаемся по дереву для поиска или нахождения заданного элемента или ключа в дереве или для вывода всех содержащихся в нем значений.

Обход по порядку

В этом методе обхода сначала посещается левое поддерево, затем корень, а затем правое поддерево. Мы всегда должны помнить, что каждый узел может представлять собой поддерево.

Если пройдено двоичное дерево in-order, вывод будет производить отсортированные ключевые значения в порядке возрастания.

Мы начинаем с 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, щелкните здесь .