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

Прохождение бинарных деревьев

Читайте также:
  1. Анализ методом деревьев событий и отказов
  2. Вопрос №7. Прохождение ГГС
  3. Классы бинарных соединений от типа неметалла
  4. ЛИЧНОЕ ПРОХОЖДЕНИЕ ГРУППОВОЙ ТЕРАПИИ
  5. Медсестра ввела сделала пациенту инъекцию препарата в вену на руке. Определите последовательность прохождение молекулами препарата элементов сосудистого русла
  6. Может ли вуз установить минимальное количество баллов, подтверждающее успешное прохождение вступительных испытаний, выше установленного учредителем?
  7. Например, отдельно стоящее дерево или группа деревьев (растение-эдификатор) и связанные с ним организмы. Биоценоз — это система связанных между собой консорций.
  8. Обработка бинарных файлов
  9. От деревьев до первых поселений
  10. Перегрузка операций. Понятие перегрузки операторов. Синтаксис перегрузки операции. Перегрузка бинарных операций, операций сравнения.
  11. Подбор и размещение деревьев и кустарников на участке детского сада
  12. Представление бинарных деревьев

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

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

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

2. пройти в прямом порядке левое поддерево

3. пройти в прямом порядке правое поддерево

Рис.4.6. Прямой порядок прохождения бинарного дерева

Прохождение бинарного дерева в обратном порядке можно определить в аналогичной форме

1. пройти в обратном порядке левое поддерево

2. пройти в обратном порядке правое поддерево

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

Рис.4.7. Обратный порядок прохождения бинарного дерева

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

1. пройти в симметричном порядке левое поддерево

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

3. пройти в симметричном порядке правое поддерево

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

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

Рис.4.8. Представление симметрично прошитого бинарного дерева в виде массивов

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


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 |

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

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