Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Прохождение деревьев

Читайте также:
  1. БИТВА ДЕРЕВЬЕВ
  2. Гарантии, предоставляемые офицерам, совмещающим прохождение военной службы с обучением в гражданских образовательных организациях
  3. На выполнение мероприятий по сносу «деревьев-угроз» находящихся на придомовых территориях, не входящих в состав общего имущества многоквартирных домов согласно адресному списку
  4. Наблюдение за корой деревьев.
  5. Основные определения. Способы изображения деревьев
  6. Предприятия и КФХ, с которыми заключены договора на прохождение производственной практики в 2013-2014 учебном году

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

Алгоритм обхода в прямом порядке:

· Попасть в корень,

· Пройти все поддеревья слева на право в прямом порядке.

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

В частности для дерева на рис. 3 и 4 прямой обход дает последовательность узлов: A, B, C, D, E, G, H.

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

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

  // Preorder Traversal – английское название для прямого порядка procedure PreorderTraversal({Аргументы}); begin //Прохождение корня DoSomething({Аргументы});   //Прохождение левого поддерева if {Существует левое поддерево} then PreorderTransversal({Аргументы 2});   //Прохождение правого поддерева if {Существует правое поддерево} then PreorderTransversal({Аргументы 3}); end;

То есть сначала процедура производит все действия, а только затем происходят все рекурсивные вызовы.[10]

Алгоритм обхода в обратном порядке:

· Пройти левое поддерево,

· Попасть в корень,

· Пройти следующее за левым поддерево.

· Попасть в корень,

· и т.д пока не будет пройдено крайнее правое поддерево.

То есть проходятся все поддеревья слева на право, а возвращение в корень располагается между этими прохождениями. Для дерева на рис. 3 и 4 это дает последовательность узлов: B, A, D, C, E, G, F.

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

  // Inorder Traversal – английское название для обратного порядка procedure InorderTraversal({Аргументы}); begin //Прохождение левого поддерева if {Существует левое поддерево} then InorderTraversal({Аргументы 2});   //Прохождение корня DoSomething({Аргументы});   //Прохождение правого поддерева if {Существует правое поддерево} then InorderTraversal({Аргументы 3}); end;

Алгоритм обхода в концевом порядке:

· Пройти все поддеревья слева на право,

· Попасть в корень.

Для дерева на рис. 3 и 4 это даст последовательность узлов: B, D, E, G, F, C, A.[11]

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


Дата добавления: 2015-08-09; просмотров: 71 | Нарушение авторских прав


Читайте в этой же книге: Введение. | Сущность рекурсии | Сложная рекурсия | Пример 2. | Рекуррентные соотношения. Рекурсия и итерация | Примеры рекурсивных алгоритмов | Ханойские башни | Синтаксический анализ арифметических выражений | Быстрые сортировки | Задачи на графах |
<== предыдущая страница | следующая страница ==>
Основные определения. Способы изображения деревьев| Представление дерева в памяти компьютера

mybiblioteka.su - 2015-2024 год. (0.008 сек.)