Презентация "Деревья. Бинарные деревья" (11 класс (углубленный уровень)

Деревья. Бинарное дерево. Деревья поиска

11 класс (профильный уровень) Болгова Н.А.

МБОУ СОШ с.Тербуны)

Определения:

• Дерево — это граф, в котором нет циклов или иерархическая структура данных, отражающая отношения подчинённости или многоуровневые связи.
• Состав дерева : узел (объект дерева);

• ребра (линии, которые соединяют узлы).

Определения:

• Бинарное (двоичное) дерево — это динамическая структура данных, представляющее собой дерево, в котором каждая вершина имеет не более двух потомков.

Свойства бинарного дерева :

• левое и правое поддерево являются двоичными деревьями поиска;

• для каждого узла X все узлы в  левом поддереве имеют значения меньше X , а в  правом поддереве — больше X.

Бинарное дерево

Обход дерева (поиск по дереву)

процесс посещения всех узлов дерева в определённом порядке.

Обход дерева в глубину :

Центрированный (ЛКП):левое –корень - правое

4 -2- 5- 1- 3

Инфиксная форм

(симметричная)

Обход дерева в глубину :

Прямой (КЛП) :корень – левое - правое

1- 2 -4- 5- 3

Префиксная форма

(операция перед данными)

Обход дерева в глубину :

Обратный (ЛПК):левое -правое- корень

4 -5- 2- 3- 1

Постфиксная форма

(операция после данных)

Обход дерева в ширину : 1 2 3 4 5

Слева – направо, - сверху - вниз

Практика

(а + 20) * 6 - 4 * b

• Построить дерево, определите узлы
• Записать все варианты обхода дерева

Решение:

1) Порядок действий

2) Строим дерево

3) Формы обхода

В ширину: - 8 * * + 6 4 b a 20

4) Формы обхода

В глубину:

1) Инфиксная форма (ЛКП) :

a + 20 * 6 - 4 * b

4) Формы обхода

В глубину:

2) Префиксная форма (КЛП ) : (операция перед данными)

- * + a 20 6 * 4 b

4) Формы обхода

В глубину:

3) Постфиксная форма (ЛПК ) : (операция после данных)

a 20 + 6 * 4 b * -

Домашнее задание

§ 39 (Стр. 80-84),

построить дерево и запишите все варианты обхода (формы записи)

56 + 23 * 3 - (24 : 2 - 5)

Литература

• Подробнее на «Облако знаний»: https:// oblakoz.ru/conspect/491059/derevya-dvoichnye-derevya
• Яндекс учебник, 11 класс,«Деревья»