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

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

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

Как правило, мы пересекаем дерево, чтобы найти или найти данный элемент или ключ в дереве или распечатать все содержащиеся в нем значения.

Порядок обхода

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

Если двоичное дерево просматривается по порядку , выходные данные будут генерировать отсортированные значения ключа в порядке возрастания.

В порядке обхода

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