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

Нажмите для полного просмотра!

Деревья. Построение дерева двоичного поиска, слайд №1

Деревья. Построение дерева двоичного поиска, слайд №2

Деревья. Построение дерева двоичного поиска, слайд №3

Деревья. Построение дерева двоичного поиска, слайд №4

Деревья. Построение дерева двоичного поиска, слайд №5

Деревья. Построение дерева двоичного поиска, слайд №6

Деревья. Построение дерева двоичного поиска, слайд №7

Деревья. Построение дерева двоичного поиска, слайд №8

Деревья. Построение дерева двоичного поиска, слайд №9

Деревья. Построение дерева двоичного поиска, слайд №10

Деревья. Построение дерева двоичного поиска, слайд №11

Деревья. Построение дерева двоичного поиска, слайд №12

Деревья. Построение дерева двоичного поиска, слайд №13

Деревья. Построение дерева двоичного поиска, слайд №14

Деревья. Построение дерева двоичного поиска, слайд №15

Деревья. Построение дерева двоичного поиска, слайд №16

Деревья. Построение дерева двоичного поиска, слайд №17

Деревья. Построение дерева двоичного поиска, слайд №18

Деревья. Построение дерева двоичного поиска, слайд №19

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Деревья. Построение дерева двоичного поиска. Доклад-сообщение содержит 19 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Деревья Лекция 5

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

Обходы деревьев в глубину Пусть T – дерево, r- корень, v1, v2,…, vn – сыновья вершины r. Прямой (префиксный ) обход: посетить корень r; посетить в прямом порядке поддеревья с корнями v1, v2,…, vn . Обратный (постфиксный) обход: посетить в обратном порядке поддеревья с корнями v1, v2,…, vn; посетить корень r. Внутренний ( инфиксный) обход для бинарных деревьев: посетить во внутреннем порядке левое поддерево корня r (если существует); посетить корень r; посетить во внутреннем порядке правое поддерево корня r (если существует).

Слайд 4

Описание слайда:

Обходы деревьев в глубину. Пример 1. Прямой Обратный Внутренний

Слайд 5

Описание слайда:

Обходы деревьев в глубину. Пример 2 + * a – d e / + f g c - префиксный обход a d e – * f g + c / + - постфиксный обход a * (d – e)+ (f + g) / c - инфиксный обход

Слайд 6

Описание слайда:

Обход дерева в ширину - это обход вершин дерева по уровням, начиная от корня, слева направо (или справа налево). Алгоритм обхода дерева в ширину Шаг 0: Поместить в очередь корень дерева. Шаг 1: Взять из очереди очередную вершину. Поместить в очередь всех ее сыновей по порядку слева направо (справа налево). Шаг 2: Если очередь пуста, то конец обхода, иначе перейти на Шаг 1.

Слайд 7

Описание слайда:

Обход дерева в ширину. Пример

Слайд 8

Описание слайда:

Представления деревьев Определение. Левое скобочное представление дерева Т (обозначается Lrep(Т)) можно получить, применяя к нему следующие рекурсивные правила: Если корнем дерева Т служит вершина а с поддеревьями T1, Т2, . . ., Тn, расположенными в этом порядке (их корни — прямые потомки вершины а), то Lrep(Т) = а (Lrep (T1), Lrep (Т2) , . . ., Lrep (Тn)) (2) Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то Lrep (Т) = а. Определение. Правое скобочное представление Rrep(Т) дерева Т: Если корнем дерева Т служит вершина а с поддеревьями T1, Т2, . . ., Тn, то Rrep(Т) = (Rrep(Т1), Rrep(T2), . . ., Rrep (Тn))а. (2) Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то Rrep(T) = а.

Слайд 9

Описание слайда:

Скобочные представления деревьев 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

Слайд 10

Описание слайда:

Представление дерева списком прямых предков Составляется список прямых предков для вершин дерева c номерами 1, 2, ..., n (именно в этом порядке). Чтобы опознать корень, будем считать, что его предок—это 0.

Слайд 11

Описание слайда:

Дерево двоичного поиска Определение. Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом l(v)S так, что l(u) < l(v) для каждого узла u из левого поддерева узла v, l(w) > l(v) для каждого узла w из правого поддерева узла v, для любого элемента a S существует единственный узел v , такой что l(v) = a.

Слайд 12

Описание слайда:

Дерево двоичного поиска. Пример Пусть S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Слайд 13

Описание слайда:

Алгоритм просмотра дерева двоичного поиска Вход: Дерево T двоичного поиска для множества S, элемент a. Выход: true если aS, false - в противном случае. Метод: Если T = , то выдать false, иначе выдать ПОИСК (a, r), где r – корень дерева T. функция ПОИСК (a, v) : boolean { если a = l(v) то выдать true иначе если a

Слайд 14

Описание слайда:

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

Слайд 15

$Реализация бинарных деревьев на Си typedef struct node { char *word; struct node *left; struct node * right; } tree; void print_tree (tree *t) { if...$

Описание слайда:

Реализация бинарных деревьев на Си 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 (“%s\n”, t->word); print_tree(t->right); }

Слайд 16

Описание слайда:

Сбалансированные деревья Теорема. Среднее число сравнений, необходимых для вставки n случайных элементов в дерево двоичного поиска, пустое в начале, равно O(n log2n) для n ≥ 1 . (без доказательства). Максимальное число сравнений O(n2) – для вырожденных деревьев. Определение. Дерево называется сбалансированным тогда и только тогда, когда высоты двух поддеревьев каждой из его вершин отличаются не более чем на единицу. АВЛ-деревья (1964 г. - Г.М.Адельсон-Вельский, Е.М. Ландис)

Слайд 17

Описание слайда:

Вставка элемента в сбалансированное дерево Пусть r – корень, L – левое поддерево, R – правое поддерево. Предположим, что включение в L приведет к увеличению высоты на 1. Возможны три случая: hL = hR hL < hR hL > hR →нарушен принцип сбалансированности, дерево нужно перестраивать