Презентация «Деревья. Построение дерева двоичного поиска»

Смотреть слайды в полном размере
Презентация «Деревья. Построение дерева двоичного поиска»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 19 слайдов и доступен в формате ppt. Размер файла: 103.78 KB

Просмотреть и скачать

Pic.1
Деревья Лекция 5
Деревья Лекция 5
Pic.2
Обходы дерева Обход дерева – это способ методичного исследования узлов дерева, при котором каждый уз
Обходы дерева Обход дерева – это способ методичного исследования узлов дерева, при котором каждый узел проходится только один раз. в глубину Обходы в ширину
Pic.3
Обходы деревьев в глубину Пусть T – дерево, r- корень, v1, v2,…, vn – сыновья вершины r. Прямой (пре
Обходы деревьев в глубину Пусть T – дерево, r- корень, v1, v2,…, vn – сыновья вершины r. Прямой (префиксный ) обход: посетить корень r; посетить в прямом порядке поддеревья с корнями v1, v2,…, vn . …
Pic.4
Обходы деревьев в глубину. Пример 1. Прямой Обратный Внутренний
Обходы деревьев в глубину. Пример 1. Прямой Обратный Внутренний
Pic.5
Обходы деревьев в глубину. Пример 2 + * a – d e / + f g c - префиксный обход a d e – * f g + c / + -
Обходы деревьев в глубину. Пример 2 + * a – d e / + f g c - префиксный обход a d e – * f g + c / + - постфиксный обход a * (d – e)+ (f + g) / c - инфиксный обход
Pic.6
Обход дерева в ширину - это обход вершин дерева по уровням, начиная от корня, слева направо (или спр
Обход дерева в ширину - это обход вершин дерева по уровням, начиная от корня, слева направо (или справа налево). Алгоритм обхода дерева в ширину Шаг 0: Поместить в очередь корень дерева. Шаг 1: Взять …
Pic.7
Обход дерева в ширину. Пример
Обход дерева в ширину. Пример
Pic.8
Представления деревьев Определение. Левое скобочное представление дерева Т (обозначается Lrep(Т)) мо
Представления деревьев Определение. Левое скобочное представление дерева Т (обозначается Lrep(Т)) можно получить, применяя к нему следующие рекурсивные правила: Если корнем дерева Т служит вершина а …
Pic.9
Скобочные представления деревьев Lrep(T) = b ( h ( a, j ( d ) ), i ( k ( e, f, g ), l ) ) Rrep(T) =
Скобочные представления деревьев Lrep(T) = b ( h ( a, j ( d ) ), i ( k ( e, f, g ), l ) ) Rrep(T) = ( ( a, ( d ) j ) h, ( ( e, f, g ) k, l ) i ) b
Pic.10
Представление дерева списком прямых предков Составляется список прямых предков для вершин дерева c н
Представление дерева списком прямых предков Составляется список прямых предков для вершин дерева c номерами 1, 2, . . . , n (именно в этом порядке). Чтобы опознать корень, будем считать, что его …
Pic.11
Дерево двоичного поиска Определение. Деревом двоичного поиска для множества S называется помеченное
Дерево двоичного поиска Определение. Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом l(v)S так, что l(u) < l(v) для …
Pic.12
Дерево двоичного поиска. Пример Пусть S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Дерево двоичного поиска. Пример Пусть S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Pic.13
Алгоритм просмотра дерева двоичного поиска Вход: Дерево T двоичного поиска для множества S, элемент
Алгоритм просмотра дерева двоичного поиска Вход: Дерево T двоичного поиска для множества S, элемент a. Выход: true если aS, false - в противном случае. Метод: Если T = , то выдать false, иначе …
Pic.14
Лабораторная работа: построение дерева двоичного поиска Вход: последовательность слов произвольной д
Лабораторная работа: построение дерева двоичного поиска Вход: последовательность слов произвольной длины (либо с клавиатуры, либо из файла) Выход: введенные слова выдаются в лексикографическом …
Pic.15
Реализация бинарных деревьев на Си typedef struct node { char *word; struct node *left; struct node
Реализация бинарных деревьев на Си typedef struct node { char *word; struct node *left; struct node * right; } tree; void print_tree (tree *t) { if (!t) return; print_tree(t->left); printf …
Pic.16
Сбалансированные деревья Теорема. Среднее число сравнений, необходимых для вставки n случайных элеме
Сбалансированные деревья Теорема. Среднее число сравнений, необходимых для вставки n случайных элементов в дерево двоичного поиска, пустое в начале, равно O(n log2n) для n ≥ 1 . (без доказательства). …
Pic.17
Вставка элемента в сбалансированное дерево Пусть r – корень, L – левое поддерево, R – правое поддере
Вставка элемента в сбалансированное дерево Пусть r – корень, L – левое поддерево, R – правое поддерево. Предположим, что включение в L приведет к увеличению высоты на 1. Возможны три случая: hL = hR …
Pic.18
Вставка в левое поддерево
Вставка в левое поддерево
Pic.19
Вставка в правое поддерево
Вставка в правое поддерево


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!