🗊Презентация Деревья. Формальное определение дерева

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Деревья. Формальное определение дерева, слайд №1Деревья. Формальное определение дерева, слайд №2Деревья. Формальное определение дерева, слайд №3Деревья. Формальное определение дерева, слайд №4Деревья. Формальное определение дерева, слайд №5Деревья. Формальное определение дерева, слайд №6Деревья. Формальное определение дерева, слайд №7Деревья. Формальное определение дерева, слайд №8Деревья. Формальное определение дерева, слайд №9Деревья. Формальное определение дерева, слайд №10Деревья. Формальное определение дерева, слайд №11Деревья. Формальное определение дерева, слайд №12Деревья. Формальное определение дерева, слайд №13Деревья. Формальное определение дерева, слайд №14Деревья. Формальное определение дерева, слайд №15Деревья. Формальное определение дерева, слайд №16Деревья. Формальное определение дерева, слайд №17Деревья. Формальное определение дерева, слайд №18Деревья. Формальное определение дерева, слайд №19Деревья. Формальное определение дерева, слайд №20Деревья. Формальное определение дерева, слайд №21Деревья. Формальное определение дерева, слайд №22Деревья. Формальное определение дерева, слайд №23Деревья. Формальное определение дерева, слайд №24Деревья. Формальное определение дерева, слайд №25Деревья. Формальное определение дерева, слайд №26Деревья. Формальное определение дерева, слайд №27Деревья. Формальное определение дерева, слайд №28Деревья. Формальное определение дерева, слайд №29Деревья. Формальное определение дерева, слайд №30Деревья. Формальное определение дерева, слайд №31Деревья. Формальное определение дерева, слайд №32Деревья. Формальное определение дерева, слайд №33Деревья. Формальное определение дерева, слайд №34Деревья. Формальное определение дерева, слайд №35Деревья. Формальное определение дерева, слайд №36Деревья. Формальное определение дерева, слайд №37Деревья. Формальное определение дерева, слайд №38Деревья. Формальное определение дерева, слайд №39Деревья. Формальное определение дерева, слайд №40Деревья. Формальное определение дерева, слайд №41Деревья. Формальное определение дерева, слайд №42Деревья. Формальное определение дерева, слайд №43Деревья. Формальное определение дерева, слайд №44
Скачать

Содержание ▲

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

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

Слайд 1


Деревья Разработала Бубнова Надежда Дмитриевна
Описание слайда:
Деревья Разработала Бубнова Надежда Дмитриевна

Слайд 2


Пример дерева
Описание слайда:
Пример дерева

Слайд 3


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

Слайд 4


Формальное определение дерева Один узел является деревом. Этот же узел также является корнем этого дерева. Пусть 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 .
Описание слайда:
Формальное определение дерева Один узел является деревом. Этот же узел также является корнем этого дерева. Пусть 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


Термины Все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама вершина – предком. Для каждого предка может быть выделено несколько потомков(отец, сыновья) Определение уровня 1. Уровень корня равен 1 2. Уровень потомка на единицу превосходит уровень его предка.
Описание слайда:
Термины Все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама вершина – предком. Для каждого предка может быть выделено несколько потомков(отец, сыновья) Определение уровня 1. Уровень корня равен 1 2. Уровень потомка на единицу превосходит уровень его предка.

Слайд 6


Высота дерева Определение Высота (глубина) дерева равна максимальному уровню вершины в дереве. Примечание Высота пустого дерева равна нулю, высота дерева из одного корня – единице.
Описание слайда:
Высота дерева Определение Высота (глубина) дерева равна максимальному уровню вершины в дереве. Примечание Высота пустого дерева равна нулю, высота дерева из одного корня – единице.

Слайд 7


Деревья высоты 4
Описание слайда:
Деревья высоты 4

Слайд 8


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

Слайд 9


Типы деревьев По величине степени выделены два типа деревьев: двоичные – степень дерева не более двух; сильноветвящиеся – степень дерева произвольна
Описание слайда:
Типы деревьев По величине степени выделены два типа деревьев: двоичные – степень дерева не более двух; сильноветвящиеся – степень дерева произвольна

Слайд 10


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

Слайд 11


Типы бинарных деревьев
Описание слайда:
Типы бинарных деревьев

Слайд 12


Типы бинарных деревьев строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов); нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов); полные – на всех уровнях, кроме последнего, узлы степени 2, а на последнем – степени 0.
Описание слайда:
Типы бинарных деревьев строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов); нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов); полные – на всех уровнях, кроме последнего, узлы степени 2, а на последнем – степени 0.

Слайд 13


Представление бинарных деревьев в памяти Списковая структура Векторное представление
Описание слайда:
Представление бинарных деревьев в памяти Списковая структура Векторное представление

Слайд 14


Представление бинарных деревьев списковой структурой
Описание слайда:
Представление бинарных деревьев списковой структурой

Слайд 15


Представление бинарных деревьев в векторной памяти
Описание слайда:
Представление бинарных деревьев в векторной памяти

Слайд 16


Информация в узле бинарного дерева информационное поле (ключ вершины); служебное поле (их может быть несколько или ни одного); указатель на левое поддерево; указатель на правое поддерево.
Описание слайда:
Информация в узле бинарного дерева информационное поле (ключ вершины); служебное поле (их может быть несколько или ни одного); указатель на левое поддерево; указатель на правое поддерево.

Слайд 17


Термины Длина пути от корня до узла соответствует уровню узла. Длина внутреннего пути – сумма длин путей до всех узлов дерева(их иногда называют внутренними). Внешний узел – обозначение позиции вставки нового узла в бинарном дереве. Длина внешнего пути – сумма длин путей до всех внешних узлов дерева.
Описание слайда:
Термины Длина пути от корня до узла соответствует уровню узла. Длина внутреннего пути – сумма длин путей до всех узлов дерева(их иногда называют внутренними). Внешний узел – обозначение позиции вставки нового узла в бинарном дереве. Длина внешнего пути – сумма длин путей до всех внешних узлов дерева.

Слайд 18


Пример внешних узлов Внешние узлы помечены NULL
Описание слайда:
Пример внешних узлов Внешние узлы помечены NULL

Слайд 19


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

Слайд 20


Пример дерева поиска
Описание слайда:
Пример дерева поиска

Слайд 21


Операции с двоичными деревьями(деревья поиска) Поиск в дереве; Обход дерева; Включение узла в дерево; Удаление узла из дерева.
Описание слайда:
Операции с двоичными деревьями(деревья поиска) Поиск в дереве; Обход дерева; Включение узла в дерево; Удаление узла из дерева.

Слайд 22


Поиск в дереве. Алгоритм Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева: если ключи совпадают, поиск завершен; если ключ в корне больше искомого, выполнить поиск в левом поддереве; если ключ в корне меньше искомого, выполнить поиск в правом поддереве. если дерево пусто, то искомый элемент не найден.
Описание слайда:
Поиск в дереве. Алгоритм Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева: если ключи совпадают, поиск завершен; если ключ в корне больше искомого, выполнить поиск в левом поддереве; если ключ в корне меньше искомого, выполнить поиск в правом поддереве. если дерево пусто, то искомый элемент не найден.

Слайд 23


Обходы дерева прямой, обратный , симметричный обходы. 
Описание слайда:
Обходы дерева прямой, обратный , симметричный обходы. 

Слайд 24


Прямой обход Если дерево T является нулевым деревом, то в список обхода записывается пустая строка; Если дерево T состоит из одного узла, то в список обхода записывается этот узел; Сначала посещается корень n , в прямом порядке посещаются узлы левого поддерева, в прямом порядке посещаются узлы правого поддерева
Описание слайда:
Прямой обход Если дерево T является нулевым деревом, то в список обхода записывается пустая строка; Если дерево T состоит из одного узла, то в список обхода записывается этот узел; Сначала посещается корень n , в прямом порядке посещаются узлы левого поддерева, в прямом порядке посещаются узлы правого поддерева

Слайд 25


Деревья. Формальное определение дерева, слайд №25
Описание слайда:

Слайд 26


Обратный обход .  Если дерево T является нулевым деревом, то в список обхода записывается пустая строка; Если дерево T состоит из одного узла, то в список обхода записывается этот узел; Посещаются в обратном порядке все узлы левого поддерева, Посещаются в обратном порядке все узлы правого поддерева, посещается корень n .
Описание слайда:
Обратный обход .  Если дерево T является нулевым деревом, то в список обхода записывается пустая строка; Если дерево T состоит из одного узла, то в список обхода записывается этот узел; Посещаются в обратном порядке все узлы левого поддерева, Посещаются в обратном порядке все узлы правого поддерева, посещается корень n .

Слайд 27


Деревья. Формальное определение дерева, слайд №27
Описание слайда:

Слайд 28


Симметричный обход .  Если дерево T является нулевым деревом, то в список обхода записывается пустая строка; Если дерево T состоит из одного узла, то в список обхода записывается этот узел; В симметричном порядке посещаются все узлы левого поддерева, Посещается корень, В симметричном порядке посещаются все узлы правого поддерева.
Описание слайда:
Симметричный обход .  Если дерево T является нулевым деревом, то в список обхода записывается пустая строка; Если дерево T состоит из одного узла, то в список обхода записывается этот узел; В симметричном порядке посещаются все узлы левого поддерева, Посещается корень, В симметричном порядке посещаются все узлы правого поддерева.

Слайд 29


Деревья. Формальное определение дерева, слайд №29
Описание слайда:

Слайд 30


 Вставка узла в дерево поиска(алгоритм) Для того чтобы вставить узел, необходимо найти его место. Сравним вставляемый ключ с корнем, если ключ больше, чем ключ корня, и правый потомок есть, уходим в правое поддерево, а иначе, при условии существования левого потомка -в левое. Если потомков нет – дошли до позиции вставки. Выполняем пункт 1, пока не дойдем до позиции вставки. Сравниваем вставляемый ключ с ключом найденного узла. Если ключ меньше ключа найденного узла, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.
Описание слайда:
 Вставка узла в дерево поиска(алгоритм) Для того чтобы вставить узел, необходимо найти его место. Сравним вставляемый ключ с корнем, если ключ больше, чем ключ корня, и правый потомок есть, уходим в правое поддерево, а иначе, при условии существования левого потомка -в левое. Если потомков нет – дошли до позиции вставки. Выполняем пункт 1, пока не дойдем до позиции вставки. Сравниваем вставляемый ключ с ключом найденного узла. Если ключ меньше ключа найденного узла, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.

Слайд 31


Пример вставки ключа 5
Описание слайда:
Пример вставки ключа 5

Слайд 32


Удаление узла Рассмотрим ситуации Удаление листа
Описание слайда:
Удаление узла Рассмотрим ситуации Удаление листа

Слайд 33


Описание ситуации(нет потомков) Если узел является конечным (то есть не имеет потомков), то его удаление не вызывает трудностей, достаточно обнулить соответствующий указатель узла-родителя
Описание слайда:
Описание ситуации(нет потомков) Если узел является конечным (то есть не имеет потомков), то его удаление не вызывает трудностей, достаточно обнулить соответствующий указатель узла-родителя

Слайд 34


Удаление узла, имеющего одного потомка
Описание слайда:
Удаление узла, имеющего одного потомка

Слайд 35


Описание ситуации(1 потомок) Потомок удаляемого узла становится тем же потомком отца удаляемого узла, каким был удаляемый узел
Описание слайда:
Описание ситуации(1 потомок) Потомок удаляемого узла становится тем же потомком отца удаляемого узла, каким был удаляемый узел

Слайд 36


Удаление узла с двумя потомками(1-простая ситуация)
Описание слайда:
Удаление узла с двумя потомками(1-простая ситуация)

Слайд 37


Описание ситуации Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а его левый потомок подключается вместо отсутствующего левого потомка к замещающему узлу.
Описание слайда:
Описание ситуации Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а его левый потомок подключается вместо отсутствующего левого потомка к замещающему узлу.

Слайд 38


Удаление узла с двумя потомками(2)
Описание слайда:
Удаление узла с двумя потомками(2)

Слайд 39


Описание ситуации В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска. Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.
Описание слайда:
Описание ситуации В общем же случае на место удаляемого узла ставится самый левый лист его правого поддерева (или наоборот – самый правый лист его левого поддерева). Это не нарушает свойств дерева поиска. Корень дерева удаляется по общему правилу за исключением того, что заменяющий его узел не требуется присоединять к узлу-родителю.

Слайд 40


Комментарии к удалению(1) В функцию del передаются указатель root на корень дерева и ключ key удаляемого элемента. С помощью функции find определяются указатели на удаляемый элемент p и его предка parent . Если искомого элемента в дереве нет, то выдается сообщение ( {6}) .
Описание слайда:
Комментарии к удалению(1) В функцию del передаются указатель root на корень дерева и ключ key удаляемого элемента. С помощью функции find определяются указатели на удаляемый элемент p и его предка parent . Если искомого элемента в дереве нет, то выдается сообщение ( {6}) .

Слайд 41


Комментарии к удалению(2) В операторах определяется указатель на узел y , который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева. Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева. В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk , выполняющая спуск по дереву.
Описание слайда:
Комментарии к удалению(2) В операторах определяется указатель на узел y , который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева. Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева. В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk , выполняющая спуск по дереву.

Слайд 42


Комментарии к удалению(3) В функции spusk первым делом проверяется особый случай, описанный выше. Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл, на каждой итерации которого указатель на текущий элемент запоминается в переменной pred , а указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка (он-то нам и нужен).
Описание слайда:
Комментарии к удалению(3) В функции spusk первым делом проверяется особый случай, описанный выше. Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл, на каждой итерации которого указатель на текущий элемент запоминается в переменной pred , а указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка (он-то нам и нужен).

Слайд 43


Комментарии к удалению(4) В операторе к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла, требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y , заменяющего удаляемый, поскольку этот узел перейдет на новое место. Функция spusk возвращает указатель на узел, заменяющий удаляемый.
Описание слайда:
Комментарии к удалению(4) В операторе к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла, требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y , заменяющего удаляемый, поскольку этот узел перейдет на новое место. Функция spusk возвращает указатель на узел, заменяющий удаляемый.

Слайд 44


Комментарии к удалению(5) Если мы удаляем корень дерева, надо обновить указатель на корень, иначе – присоединить этот указатель к соответствующему поддереву предка удаляемого узла. После того как узел удален из дерева, освобождается занимаемая им память.
Описание слайда:
Комментарии к удалению(5) Если мы удаляем корень дерева, надо обновить указатель на корень, иначе – присоединить этот указатель к соответствующему поддереву предка удаляемого узла. После того как узел удален из дерева, освобождается занимаемая им память.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию