Содержание
- 2. БИНАРНОЕ ДЕРЕВО
- 3. Понятие бинарного дерева Эта динамическая структура данных состоит из узлов (вершин), каждый из которых содержит, кроме
- 4. Терминология Узел(вершина) дерева – каждый элемент дерева. Корень дерева- начальный узел. Ветви дерева – вершины дерева
- 5. Терминология Бинарное (двоичное) дерево – это дерево, в котором каждая вершина имеет не более двух потомков.
- 6. БИНАРНОЕ УПОРЯДОЧЕННОЕ ДЕРЕВО
- 7. Бинарное упорядоченное дерево (дерево поиска) Если дерево организовано таким образом, что для каждого узла все ключи
- 8. Пример построение дерева поиска Бинарное упорядоченное дерево по приходящим числам: 17, 18, 6, 5, 9, 23,
- 9. ИДЕАЛЬНО СБАЛАНСИРОВАННОЕ ДЕРЕВО
- 10. Идеально сбалансированное дерево Идеально сбалансированным дерево - это дерево, в котором число узлов (вершин) в левом
- 11. Идеально сбалансированное дерево Алгоритм равномерного распределения для известного числа вершин формулируют, используя рекурсию. 1. Взять одну
- 12. Идеально сбалансированное дерево
- 13. ОПЕРАЦИИ С БИНАРНЫМ УПОРЯДОЧЕННЫМ ДЕРЕВОМ 1.УДАЛЕНИЕ УЗЛА ИЗ ДЕРЕВА
- 14. Исключаемый узел – лист. Действия: Удалить ссылку на данный узел.
- 15. Из исключаемого узла выходит одна ветвь. Действия: переназначить указатель (пунктир).
- 16. Из исключаемого узла выходят две ветви Действия: на место удаляемого узла надо поставить либо самый правый
- 17. ОПЕРАЦИИ С БИНАРНЫМ УПОРЯДОЧЕННЫМ ДЕРЕВОМ 2. ОБХОД (ПРОСМОТР) ДЕРЕВА
- 18. Обходы (просмотры) дерева Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается
- 19. Способы обхода (просмотра) дерева а) Просмотр слева-направо: ARB (левое поддерево-корень-правое поддерево). б) Просмотр сверху-вниз: RAB (корень
- 20. Пример обхода дерева а) ARB: - инфиксная запись. б) RAB: - префиксная запись. в) ABR: -
- 22. Скачать презентацию