Содержание
- 2. Деревья
- 3. Деревья Дерево – это структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем
- 4. Деревья Предок узла x – это узел, из которого существует путь по стрелкам в узел x.
- 5. Дерево – рекурсивная структура данных Рекурсивное определение: Пустая структура – это дерево. Дерево – это корень
- 6. Двоичные деревья Структура узла: struct Node { int data; // полезные данные Node *left, *right; //
- 7. Двоичные деревья Многие полезные структуры данных основаны на двоичном дереве: Двоичное дерево поиска Двоичная куча АВЛ-дерево
- 8. Двоичные деревья поиска Слева от каждого узла находятся узлы с меньшими ключами, а справа – с
- 9. Двоичные деревья поиска Двоичное дерево поиска— это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства
- 10. Двоичные деревья поиска Поиск в массиве (N элементов): При каждом сравнении отбрасывается 1 элемент. Число сравнений
- 11. Несбалансированные двоичные деревья поиска (unbalanced) Это такие деревья, высота правого и левого поддеревьев которых отличаются более,
- 12. Неполные двоичные деревья поиска (incomplete) Каждый узел дерева двоичного поиска должен содержать не более 2 детей.
- 13. Основные операции в двоичном дереве поиска Базовый интерфейс двоичного дерева поиска состоит из трех операций: Поиск
- 14. Поиск элемента Дано: дерево Т и ключ K. Задача: проверить, есть ли узел с ключом K
- 15. Добавление элемента Дано: дерево Т и пара (K,V). Задача: добавить пару (K, V) в дерево Т.
- 16. Удаление узла Дано: дерево Т с корнем n и ключом K. Задача: удалить из дерева Т
- 17. Реализация алгоритма поиска //--------------------------------------- // Функция Search – поиск по дереву // Вход: Tree - адрес
- 18. Как построить дерево поиска? //--------------------------------------------- // Функция AddToTree – добавить элемент к дереву // Вход: Tree
- 19. Обход дерева Обход дерева – это перечисление всех узлов в определенном порядке. Обход ЛКП («левый –
- 20. Обход дерева – реализация //--------------------------------------------- // Функция LKP – обход дерева в порядке ЛКП // (левый
- 21. Двоичная куча Двоичная куча Структура данных для хранения двоичной кучи
- 22. Двоичная куча Двоичная куча (пирамида) — такое двоичное дерево, для которого выполнены три условия: Значение в
- 23. Кучи Max-heap Значение в любой вершине больше, чем значения ее потомков Min-heap Значение в любой вершине
- 24. Красно-чёрное дерево
- 25. Красно-чёрное дерево Красно-чёрное дерево (Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический
- 26. АВЛ-дерево АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух
- 27. B-дерево B-дерево (по-русски произносится как Б-дерево) — структура данных, дерево поиска. С точки зрения внешнего логического
- 28. Пример B-дерева степени 2
- 29. 2-3-дерево 2-3 дерево — структура данных являющаяся B-деревом степени 1, страницы которого могут содержать только 2-вершины
- 30. Разбор арифметических выражений a b + c d + 1 - / Как вычислять автоматически: Инфиксная
- 31. Вычисление выражений Постфиксная форма: a b + c d + 1 - / Алгоритм: взять очередной
- 32. Вычисление выражений Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа
- 33. Построение дерева Алгоритм: если first=last (остался один символ – число), то создать новый узел и записать
- 34. Как найти последнюю операцию? Порядок выполнения операций умножение и деление; сложение и вычитание. Приоритет (старшинство) –
- 35. Приоритет операции //-------------------------------------------- // Функция Priority – приоритет операции // Вход: символ операции // Выход: приоритет
- 36. Номер последней операции //-------------------------------------------- // Функция LastOperation – номер последней операции // Вход: строка, номера первого
- 37. Построение дерева Структура узла struct Node { char data; Node *left, *right; }; typedef Node *PNode;
- 38. Построение дерева //-------------------------------------------- // Функция MakeTree – построение дерева // Вход: строка, номера первого и последнего
- 39. Вычисление выражения по дереву //-------------------------------------------- // Функция CalcTree – вычисление по дереву // Вход: адрес дерева
- 40. Основная программа //-------------------------------------------- // Основная программа: ввод и вычисление // выражения с помощью дерева //-------------------------------------------- void
- 41. Дерево игры Задача. Перед двумя игроками лежат две кучки камней, в первой из которых 3, а
- 43. Скачать презентацию