Форма обучения

Квалификация (степень) выпускника

Профиль подготовки

Направление подготовки

История России до ХХ века

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

Эквивалентные бинарные деревья

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

Над бинарным деревом есть операция – его прохождение, т.е. нужно обойти все дерево, отметив каждый узел один раз.

Существует 3 способа обхода бинарного дерева.

1. В прямом порядке.

2. В симметричном порядке.

3. В обратном порядке.

В прямом порядке (обход в прямом порядке, прямой обход, упорядоченный обход, обход сверху, обход в ширину, preorder):

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

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

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

В симметричном порядке (обход симметричным способом, симметричный обход, inorder):

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

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

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

В обратном порядке (обход в обратном порядке, обход в глубину, обратный обход, обход снизу, postorder):

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

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

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

Дерево и лес любого вида можно преобразовать единственным образом в эквивалентное бинарное дерево.

Правило построения бинарного дерева из любого дерева:

1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение).

2. Соединить горизонтальными ребрами всех братьев одного отца.

3. Таким образом перестроить дерево по правилу:

– левый сын – вершина, расположенная под данной;

– правый сын – вершина, расположенная справа от данной (т.е. на одном ярусе с ней).

4. Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых сыновей, а горизонтальные – правых.

В результате преобразования любого дерева в бинарное получается дерево в виде левого поддерева, подвешенного к корневой вершине.

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

Правило построения бинарного дерева из леса: корни всех поддеревьев леса соединить горизонтальными связями. В полученном дереве узлы в данном примере будут располагаться на трех уровнях. Далее перестраивать по ранее рассмотренному плану. В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом.

ДИСЦИПЛИНЫ (МОДУЛЯ)

(наименование дисциплины (модуля))

________________ история 03.06.00.62 ______________

___________ Отечественная история ______________

(при наличии профиля в ООП)

Бакалавр

______________ очная _____________

(очная, очно-заочная, экстернат)

Сыктывкар 2012

СОДЕРЖАНИЕ

1. Рабочая программа дисциплины

1.1. Цель освоения учебной дисциплины

1.2. Место учебной дисциплины в структуре ООП бакалавриата

1.3. Компетенции обучающегося, формируемые в результате освоения дисциплины

1.4. Структура и содержание дисциплины

2. Образовательные технологии

3. Учебно-методическое обеспечение самостоятельной работы студентов.

Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины

3.1.Самостоятельная работа

3.2.Темы практических занятий и методические рекомендации

3.3.Вопросы для подготовки к контрольной работе

3.5.Вопросы к экзамену

4. Учебно-методическое и информационное обеспечение дисциплины

5. Материально-техническое обеспечение дисциплины

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Сыктывкарский государственный университет»

Институт гуманитарных наук

Кафедра Истории России и зарубежных стран

УТВЕРЖДЕНО

Дата добавления: 2014-11-20