Презентация Деревья. Формальное определение дерева онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Деревья. Формальное определение дерева абсолютно бесплатно. Урок-презентация на эту тему содержит всего 44 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Деревья. Формальное определение дерева
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:44 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:248.85 kB
- Просмотров:70
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№3 слайд
![Дерево это совокупность](/documents_6/99d5acc52060100d1cd756173776417b/img2.jpg)
Содержание слайда: Дерево – это совокупность элементов и отношений, образующих иерархическую структуру этих элементов.
Каждый элемент дерева называется вершиной (узлом) дерева.
Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Начальный узел дерева называют корнем дерева, ему соответствует нулевой уровень. Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви
№4 слайд
![Формальное определение дерева](/documents_6/99d5acc52060100d1cd756173776417b/img3.jpg)
Содержание слайда: Формальное определение дерева
Один узел является деревом. Этот же узел также является корнем этого дерева.
Пусть n – это узел, а T 1 , T 2 , ... T m – деревья с корнями n 1 , n 2 , … n m соответственно. Можно построить новое дерево, сделав n родителем узлов n 1 , n 2 , … n m . В этом дереве n будет корнем, а T 1 , T 2 , ... T m – поддеревьями этого корня. Узлы n 1 , n 2 , … n m называются сыновьями узла n .
№5 слайд
![Термины Все вершины, в](/documents_6/99d5acc52060100d1cd756173776417b/img4.jpg)
Содержание слайда: Термины
Все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама вершина – предком. Для каждого предка может быть выделено несколько потомков(отец, сыновья)
Определение уровня
1. Уровень корня равен 1
2. Уровень потомка на единицу превосходит уровень его предка.
№8 слайд
![Определения Поддерево часть](/documents_6/99d5acc52060100d1cd756173776417b/img7.jpg)
Содержание слайда: Определения
Поддерево – часть дерева, которая может быть представлена в виде отдельного дерева.
Степенью вершины в дереве называется количество дуг, которое из нее выходит.
Степень дерева равна максимальной степени вершин, входящих в дерево.
(При этом листьями в дереве являются вершины, имеющие нулевую степень)
№17 слайд
![Термины Длина пути от корня](/documents_6/99d5acc52060100d1cd756173776417b/img16.jpg)
Содержание слайда: Термины
Длина пути от корня до узла соответствует уровню узла.
Длина внутреннего пути – сумма длин путей до всех узлов дерева(их иногда называют внутренними).
Внешний узел – обозначение позиции вставки нового узла в бинарном дереве.
Длина внешнего пути – сумма длин путей до всех внешних узлов дерева.
№22 слайд
![Поиск в дереве. Алгоритм Если](/documents_6/99d5acc52060100d1cd756173776417b/img21.jpg)
Содержание слайда: Поиск в дереве.
Алгоритм
Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:
если ключи совпадают, поиск завершен;
если ключ в корне больше искомого, выполнить поиск в левом поддереве;
если ключ в корне меньше искомого, выполнить поиск в правом поддереве.
если дерево пусто, то искомый элемент не найден.
№24 слайд
![Прямой обход Если дерево T](/documents_6/99d5acc52060100d1cd756173776417b/img23.jpg)
Содержание слайда: Прямой обход
Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
Если дерево T состоит из одного узла, то в список обхода записывается этот узел;
Сначала посещается корень n ,
в прямом порядке посещаются узлы левого поддерева,
в прямом порядке посещаются узлы правого поддерева
№26 слайд
![Обратный обход . Если дерево](/documents_6/99d5acc52060100d1cd756173776417b/img25.jpg)
Содержание слайда: Обратный обход .
Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
Если дерево T состоит из одного узла, то в список обхода записывается этот узел;
Посещаются в обратном порядке все узлы левого поддерева,
Посещаются в обратном порядке все узлы правого поддерева,
посещается корень n .
№28 слайд
![Симметричный обход . Если](/documents_6/99d5acc52060100d1cd756173776417b/img27.jpg)
Содержание слайда: Симметричный обход .
Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
Если дерево T состоит из одного узла, то в список обхода записывается этот узел;
В симметричном порядке посещаются все узлы левого поддерева,
Посещается корень,
В симметричном порядке посещаются все узлы правого поддерева.
№30 слайд
![Вставка узла в дерево поиска](/documents_6/99d5acc52060100d1cd756173776417b/img29.jpg)
Содержание слайда: Вставка узла в дерево поиска(алгоритм)
Для того чтобы вставить узел, необходимо найти его место.
Сравним вставляемый ключ с корнем, если ключ больше, чем ключ корня, и правый потомок есть, уходим в правое поддерево, а иначе, при условии существования левого потомка -в левое. Если потомков нет – дошли до позиции вставки.
Выполняем пункт 1, пока не дойдем до позиции вставки.
Сравниваем вставляемый ключ с ключом найденного узла. Если ключ меньше ключа найденного узла, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.
№39 слайд
![Описание ситуации В общем же](/documents_6/99d5acc52060100d1cd756173776417b/img38.jpg)
Содержание слайда: Описание ситуации
В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска.
Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.
№40 слайд
![Комментарии к удалению В](/documents_6/99d5acc52060100d1cd756173776417b/img39.jpg)
Содержание слайда: Комментарии к удалению(1)
В функцию del передаются указатель root на корень дерева и ключ key удаляемого элемента. С помощью функции find определяются указатели на удаляемый элемент p и его предка parent . Если искомого элемента в дереве нет, то выдается сообщение ( {6}) .
№41 слайд
![Комментарии к удалению В](/documents_6/99d5acc52060100d1cd756173776417b/img40.jpg)
Содержание слайда: Комментарии к удалению(2)
В операторах определяется указатель на узел y , который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева.
Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева.
В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk , выполняющая спуск по дереву.
№42 слайд
![Комментарии к удалению В](/documents_6/99d5acc52060100d1cd756173776417b/img41.jpg)
Содержание слайда: Комментарии к удалению(3)
В функции spusk первым делом проверяется особый случай, описанный выше. Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл, на каждой итерации которого указатель на текущий элемент запоминается в переменной pred , а указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка (он-то нам и нужен).
№43 слайд
![Комментарии к удалению В](/documents_6/99d5acc52060100d1cd756173776417b/img42.jpg)
Содержание слайда: Комментарии к удалению(4)
В операторе к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла, требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y , заменяющего удаляемый, поскольку этот узел перейдет на новое место.
Функция spusk возвращает указатель на узел, заменяющий удаляемый.
Скачать все slide презентации Деревья. Формальное определение дерева одним архивом: