andrey

Путь к Файлу: /Документы для форматирования / Кошелев / Динамические структуры данных / Деревья.ppt

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   60
Пользователь:   andrey
Добавлен:   05.01.2015
Размер:   246.5 КБ
СКАЧАТЬ

Наверх страницы

Содержимое презентации:

Слайд 1

1 Деревья Лекция 7

Слайд 2

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

Слайд 3

3 Основная терминология книга Гл.1 Гл.2 Гл. 3 Р1.1 Р1.2 Р2.1 Р2.2 Р2.3 Р2.1.1 Р2.1.2 Корень Лист Поддерево Узел

Слайд 4

4 Основная терминология Нулевое дерево – дерево без узлов. Путем из узла n1 в узел nk – последовательность узлов n1 n2 … nk , где для всех i, 1ik, узел ni является родителем узла ni+1. Длина пути – число, на единицу меньшее числа узлов, составляющих этот путь.

Слайд 5

5 Какова длина пути от корня до Р2.3? книга Гл.1 Гл.2 Гл. 3 Р1.1 Р1.2 Р2.1 Р2.2 Р2.3 Р2.1.1 Р2.1.2 Какова длина пути от корня до Р2.1.2?

Слайд 6

6 Основная терминология Высота узла – длина самого длинного пути из этого узла до какого-либо листа Высота дерева – высота корня. Глубина узла – длина пути от корня до этого узла.

Слайд 7

7 Высота узла Гл.2= книга Гл.1 Гл.2 Гл. 3 Р1.1 Р1.2 Р2.1 Р2.2 Р2.3 Р2.1.1 Р2.1.2 Глубина узла Гл.2= 2 1

Слайд 8

8 Основная терминология Если значение левого сына меньше значения правого, то дерево называется упорядоченным. a b c a c b Упорядоченное Неупорядоченное

Слайд 9

9 Бинарное дерево Двоичное (бинарное) дерево - упорядоченное дерево, каждый узел которого имеет не более 2 сыновей.

Слайд 10

10 Описание бинарного дерева Type PTree = ^TTree; TTree = Record Data : Integer; Left, Right : PTree; end; Data – информационное поле Left, Right –указатели на левую и правую ветвь

Слайд 11

11 Описание бинарного дерева Var Tree : PTree; Корень дерева описывается ссылочной переменной:

Слайд 12

12 Описание бинарного дерева Сколько информационных полей может иметь узел дерева? Сколько ссылочных полей должен иметь узел следующего дерева? 1 2 4 6 3 5

Слайд 13

13 Основные операции над деревом •добавление элемента в дерево; •обход дерева; •удаление элемента из дерева.

Слайд 14

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

Слайд 15

15 Добавление элемента в дерево Пусть N-новый узел дерева. Алгоритм действий: •Создаем узел дерева; •Если N< каждого узла дерева, то добавляем по левой ветке иначе по правой.

Слайд 16

16 Добавление элемента в дерево 13 23 6 17 2 15 57 23>13 13 справа 23 6<13 слева 6 17<23 слева 17>13 по правой 2 17 15 57

Слайд 17

17 Добавление элемента в дерево Постройте бинарные деревья из следующего набора: • C , F, E, B, A, D; • 45, 23, 35, 17, 28, 13.

Слайд 18

18 Добавление элемента в дерево Procedure InsTree(n : lnteger; var ANode : PTree); Begin if ANode = nil then Begin new (ANode); With ANode^ do Begin Left := nil; Right := nil; Data := n; end; end else if n< ANode^.Data then InsTree(n, ANode^.Left) else InsTree(n, ANode^.Right); End; Назад

Слайд 19

19 Добавление элемента в дерево var root:PTree; answer:integer; … repeat writeln(‘Введите узел’); readln(answer); if answer<>0 then ins(answer,root); until answer=0;

Слайд 20

20 Добавление элемента в дерево • Будут ли отображаться в дереве одинаковые узлы? • Что нужно сделать, чтобы отображались? • Что необходимо изменить, чтобы меньшие узлы располагались справа, а большие слева? Код

Слайд 21

21 Просмотр узлов Вывод двоичного дерева можно производить рекурсивно, выполняя для каждой вершины три действия: • вывод числа, хранящегося в узле; • обход левого поддерева; • обход правого поддерева.

Слайд 22

22 Просмотр узлов Способы обхода: прямой обход (сверху вниз); симметричный обход (слева направо); обратный обход (снизу вверх).

Слайд 23

23 Прямой обход procedure print(ANode:Ptree); begin if ANode<>nil then begin writeln(ANode^.data); print(Anode^.left); print(ANode^.right); end; end;

Слайд 24

24 Прямой обход 13 6 23 2 17 15 57 В каком порядке выведутся элементы? if ANode<>nil then begin writeln(ANode^.data); print(Anode^.left); print(ANode^.right); end; 13 6 2 23 17 15 57

Слайд 25

25 Прямой обход 10 7 12 14 6 8 15 В каком порядке выведутся элементы? 10 7 6 9 8 12 15 14 20 9 20

Слайд 26

26 Прямой обход Сначала просматриваются левые ветви, затем по уменьшению глубины вершин правые. Значения выводятся сверху. 13 6 23 2 17 15 57 13 6 2 23 17 15 57

Слайд 27

27 Обратный обход procedure print(ANode:Ptree); begin if ANode<>nil then begin print(Anode^.left); print(ANode^.right); writeln(ANode^.data); end; end;

Слайд 28

28 Обратный обход 13 6 23 2 17 15 57 В каком порядке выведутся элементы? if ANode<>nil then begin print(Anode^.left); print(ANode^.right); writeln(ANode^.data); end; 2 6 15 17 57 23 13

Слайд 29

29 Обратный обход 10 7 12 14 6 8 15 В каком порядке выведутся элементы? 6 8 9 7 14 20 15 12 10 9 20

Слайд 30

30 Обратный обход Сначала просматриваются левые ветви, затем по уменьшению глубины вершин правые. Значения выводятся снизу. 13 6 23 2 17 15 57 2 6 15 17 57 23 13

Слайд 31

31 Симметричный обход procedure print(ANode:Ptree); begin if ANode<>nil then begin print(Anode^.left); writeln(ANode^.data); print(ANode^.right); end; end;

Слайд 32

32 Симметричный обход 13 6 23 2 17 15 57 В каком порядке выведутся элементы? if ANode<>nil then begin print(Anode^.left); writeln(ANode^.data); print(ANode^.right); end; 2 6 13 15 17 23 57

Слайд 33

33 Симметричный обход 10 7 12 14 6 8 15 В каком порядке выведутся элементы? 6 7 8 9 10 12 14 15 20 9 20

Слайд 34

34 Симметричный обход Сначала просматриваются левые ветви, затем корень поддерева, а потом правые. 13 6 23 2 17 15 57 2 6 13 15 17 23 57

Слайд 35

35 Поиск элементов Задача Из существующей базы сотрудников фирмы найти тех, чей оклад равен заданному. Для этого необходимо построить бинарное дерево, корнем которого будет средний оклад.

Слайд 36

36 Поиск элементов 6.4 7 1.5 9 10.7 20 9.1 6.4 10.7 7 1.5 20 9 Даны оклады: Бинарное дерево:

Слайд 37

37 Поиск элементов: преимущества Для нахождения необходимо сделать не более 4-х сравнений; В зависимости от поиска – строится свое бинарное дерево. При симметричном просмотре элементы отсортированы по возрастанию.

Слайд 38

38 Поиск элементов Ptree=^tree_okl; Tree_okl=record num:byte; okl:real; left, right:ptree; End; Элемент дерева: Номер элемента Значение оклада

Слайд 39

39 Поиск элементов Опишем процедуру поиска, где t – указатель на корень дерева; ok – заданное число; n – номер найденного узла

Слайд 40

40 Поиск элементов Procedure poisk_tree(t:ptree; ok:real; var n:byte); begin if t<>nil then if t.okl=ok then n:=t^.num else begin poisk_tree(t^.left, ok, n); poisk_tree(t^.right, ok, n); end; end; Сравнение и запоминание номера Дальнейший просмотр

Слайд 41

41 Удаление узла Удаление листа; Удаление узла с одним выходящим ребром; Удаление узла с двумя выходящими ребрами;

Слайд 42

42 Удаление узла : листа Если потомков нет, то вершину можно просто удалить. 13 6 23 2 17 15 57

Слайд 43

43 Удаление узла:один потомок Удаляемую вершину можно “вырезать”, заманив на имеющегося потомка 13 6 23 2 17 57 2

Слайд 44

44 Удаление узла: два потомка Заменяем на следующую за удаляемой (по порядку) вершину. 13 23 17 2 57 17

Слайд 45

45 Удаление узла Procedure Del(var R : PTree); Begin if R^.Right <> nil then Del(R. ^Right) else begin q^.Data := R^.Data; q := R; R := R^.Left; Dispose(q); end;

Слайд 46

46 Удаление узла Procedure DeleteNode(x : Integer; var ANode : PTree); Var q : PTree; {описание процедуры Del} Вegin if ANode = nil then Writeln(‘Элемента с ключом ’,x,’ в дереве нет’) else if x < ANode^.Data then DeleteNode(x,ANode^. Left) else if x > ANode^.Data then DeleteNode(x,ANode^. Right) else begin q := ANode; if q^.Right = nil then Begin ANode := q^.Left; Dispose(q); end else if q^.Left = nil then begin ANode := q^. Right; Dispose(q); end

Слайд 47

47 Удаление узла Заменяем на левый лист - 17 13 6 23 2 17 57 17 6 23 2 57

Слайд 48

48 Резюме Дерево – это … Высота узла – это … Высота дерева – это … Глубина узла – … Путем из узла n1 в узел nk – … Длина пути – … Двоичное (бинарное) дерево -…

Слайд 49

49 Резюме:операции • добавление элемента в дерево; • обход дерева; • удаление элемента из дерева.

Слайд 50

50 Резюме:операции Основное правило добавления узла заключается … Просмотр дерева включает три действия: … Существует 3 вида обхода дерева: … Прямой - … Симметричный -… Обратный - …

Слайд 51

51 Резюме:операции Свойство симметричного обхода заключается … Основная область применения бинарных деревьев - … Почему? Основное правило удаления узла заключается в …


Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

Наш сайт представляет собой Сервис, где студенты самых различных специальностей могут делиться своей учебой. Для удобства организован онлайн просмотр содержимого самых разных форматов файлов с возможностью их скачивания. У нас можно найти курсовые и лабораторные работы, дипломные работы и диссертации, лекции и шпаргалки, учебники, чертежи, инструкции, пособия и методички - можно найти любые учебные материалы. Наш полезный сервис предназначен прежде всего для помощи студентам в учёбе, ведь разобраться с любым предметом всегда быстрее когда можно посмотреть примеры, ознакомится более углубленно по той или иной теме. Все материалы на сайте представлены для ознакомления и загружены самими пользователями. Учитесь с нами, учитесь на пятерки и становитесь самыми грамотными специалистами своей профессии.

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика