Бинарные деревья. Обход в прямом порядке

Связные списки, стеки и очереди являются линейными структурами данных (это последовательности). Деревья представляют собой нелинейную двумерную структуру данных со специальными свойствами. Узлы дерева содержат две или более ссылок. В этом примере рассматриваются бинарные деревья, т.е. деревья, узлы которого содержат по две ссылки (одна или обе из которых могут быть NULL).
Корневой узел является первым узлом дерева. Каждая ссылка в корневом узле указывает на дочерний узел или узел-потомок. Левый узел-потомок является первым узлом в левом поддереве, а правый узел-потомок является первым узлом в правом поддереве. Узлы-потомки, принадлежащие одному какому-либо узлу, называются родственными узлами. Узел без узлов-потомков называется листом дерева или концевым узлом. Компьютерщики обычно рисуют деревья сверху-вниз, начиная с корневого узла, то есть противоположно тому, как растут деревья в природе.
В этом примере рассмотрим обход бинарного дерева в прямом порядке. Каждый узел посещается до того, как посещены его потомки.

Для корня дерева выполняются следующие шаги:

  • Посетить узел
  • Обойти левое поддерево
  • Обойти правое поддерево

Это может быть реализовано двумя способами

  • рекурсивно
  • итерационно (пошагово)

Шаги для итерационного решения:
Создать пустой стек и поместить в него корневой узел.
Выполните следующие действия, до тех по пока стек не пуст:
Возьмите узел из стека, и распечатайте его
Поместите правого потомка узла в стек
Поместите левого потомка узла в стек

Мы помещаем первым правого потомка, но он будет обработан после левого поддерева, так как стек организован по принципу Last In First Out (LIFO).

Результат выполнения программы:

 

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *