АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Алгоритмы обхода дерева

Читайте также:
  1. Алгоритмы
  2. Алгоритмы диагностирования и методы их построения
  3. Алгоритмы поиска дефектов
  4. Алгоритмы упорядочивания элементов в массивах
  5. Алгоритмы электронной цифровой подписи
  6. Асимметричные криптоалгоритмы
  7. Введение в стандартную библиотека шаблонов (STL): контейнеры, алгоритмы, итераторы.
  8. Использование дерева построения
  9. Итерационные алгоритмы размещения
  10. Классификация и виды уклонений и обхода налогов (криминальные и некриминальные деяния)
  11. Метод построения дерева решений

Существуют три алгоритма обхода деревьев, которые естественно следуют из самой структуры дерева.

1. Обход слева направо: Left-Root-Right (сначала посещаем левое поддерево, затем – корень и, наконец, правое поддерево).

2. Обход сверху вниз: Root-Left-Right (посещаем корень до поддеревьев).

3. Обход снизу вверх: Left-Right-Root (посещаем корень после поддеревьев).

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

Пусть для операндов А и В выполня­ется операция сложения. Привычная форма записи в виде А + В называется ин­фиксной. Форма записи, в которой знак операции следует перед операндами + АВ, называется префиксной, если же операция записывается после операндов АВ + – постфиксной.

Рассмотрим небольшой пример, пусть задано выражение А + В * С. Так как умножение имеет более высокий приоритет, то данное выражение можно переписать в виде А +(В * С). Для записи выражения в постфиксной форме сначала преобразуем ту часть выражения, которая вычисляется первой, в результате получим: А +(ВС *).

Теперь запишем в постфиксной форме операцию сложения между операндами А и (ВС *): АВС *+.

Таким образом, выражение А + В * С в постфиксном виде АВС *+, префиксная форма записи будет иметь вид +* АВС.

Рассмотрим различные обходы дерева на примере формулы: ((a + b / c)*(de * f)). Дерево формируется по принципу:

– в корне размещаем операцию, которая выполнится последней;

– далее узлы-операции, операнды – листья дерева.

Обход 1 (Left-Root-Right) дает обычную инфиксную запись выражения (без скобок):

a + b / c * de * f.

Обход 2 (Root-Left-Right) – префиксную запись выражения (без скобок):

* + a / b cd * e f.

Обход 3 (Left-Right-Root) – постфиксную запись выражения:

a b c / + d e f * – *.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)