Содержание
- 2. Пример дерева
- 3. Дерево – это совокупность элементов и отношений, образующих иерархическую структуру этих элементов. Каждый элемент дерева называется
- 4. Формальное определение дерева Один узел является деревом. Этот же узел также является корнем этого дерева. Пусть
- 5. Термины Все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама
- 6. Высота дерева Определение Высота (глубина) дерева равна максимальному уровню вершины в дереве. Примечание Высота пустого дерева
- 7. Деревья высоты 4 4 3 1 2
- 8. Определения Поддерево – часть дерева, которая может быть представлена в виде отдельного дерева. Степенью вершины в
- 9. Типы деревьев По величине степени выделены два типа деревьев: двоичные – степень дерева не более двух;
- 10. Типы деревьев Упорядоченное дерево – это дерево, у которого ветви, исходящие из каждой вершины, упорядочены по
- 11. Типы бинарных деревьев
- 12. Типы бинарных деревьев строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);
- 13. Представление бинарных деревьев в памяти Списковая структура Векторное представление
- 14. Представление бинарных деревьев списковой структурой
- 15. Представление бинарных деревьев в векторной памяти Для хранения дерева выделяется массив. Например, массив А. Корень хранится
- 16. Информация в узле бинарного дерева информационное поле (ключ вершины); служебное поле (их может быть несколько или
- 17. Термины Длина пути от корня до узла соответствует уровню узла. Длина внутреннего пути – сумма длин
- 18. Пример внешних узлов Внешние узлы помечены NULL
- 19. Дерево поиска Дерево, для каждого узла которого все ключи узлов его левого поддерева меньше ключа этого
- 20. Пример дерева поиска
- 21. Операции с двоичными деревьями(деревья поиска) Поиск в дереве; Обход дерева; Включение узла в дерево; Удаление узла
- 22. Поиск в дереве. Алгоритм Если дерево не пусто, то нужно сравнить искомый ключ с ключом в
- 23. Обходы дерева прямой, обратный , симметричный обходы.
- 24. Прямой обход Если дерево T является нулевым деревом, то в список обхода записывается пустая строка; Если
- 26. Обратный обход . Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
- 28. Симметричный обход . Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
- 30. Вставка узла в дерево поиска(алгоритм) Для того чтобы вставить узел, необходимо найти его место. Сравним вставляемый
- 31. Пример вставки ключа 5
- 32. Удаление узла Рассмотрим ситуации Удаление листа
- 33. Описание ситуации(нет потомков) Если узел является конечным (то есть не имеет потомков), то его удаление не
- 34. Удаление узла, имеющего одного потомка
- 35. Описание ситуации(1 потомок) Потомок удаляемого узла становится тем же потомком отца удаляемого узла, каким был удаляемый
- 36. Удаление узла с двумя потомками(1-простая ситуация)
- 37. Описание ситуации Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый
- 38. Удаление узла с двумя потомками(2)
- 39. Описание ситуации В общем же случае на место удаляемого узла ставится самый левый лист его правого
- 40. Комментарии к удалению(1) В функцию del передаются указатель root на корень дерева и ключ key удаляемого
- 41. Комментарии к удалению(2) В операторах определяется указатель на узел y , который должен заменить удаляемый. Если
- 42. Комментарии к удалению(3) В функции spusk первым делом проверяется особый случай, описанный выше. Если же этот
- 43. Комментарии к удалению(4) В операторе к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем
- 45. Скачать презентацию