Деревья - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

Описание слайда:

Деревья

Слайд 2

Описание слайда:

Слайд 3

Описание слайда:

Определение 1 дерево как конечное множество T, состоящее из одного или более элементов (называемых вершинами или узлами), таких, что имеется одна специально выделенная вершина, называемая корнем дерева; остальные вершины (исключая корень) содержатся в m попарно непересекающихся множествах T1,T2,...,Tm, каждое из которых, в свою очередь, является деревом. Деревья T1,T2,...Tm называются поддеревьями данного дерева. Упорядоченным деревом мы будем называть такое дерево, в котором важен порядок следования поддеревьев T1,T2,...Tm.

Слайд 4

Описание слайда:

Дуга - это ориентированная связь между двумя вершинами дерева, поэтому, например, корень можно определить как такую вершину дерева, в который не входит ни одной дуги, поэтому часто говорят, что корень - это "исходная" вершина дерева, через которую доступны остальные его вершины. Ребро - это неориентированная связь между двумя вершинами дерева. Ясно, что ребро можно превратить в дугу, если задать на нем ориентацию (направление), а любое дерево можно превратить в ориентированное дерево, если задать ориентацию ребер. Количество поддеревьев некоторой вершины называется степенью этой вершины. Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями. Вершина с нулевой степенью называется листом, иначе - она называется внутренней вершиной (внутренним узлом). Число листьев дерева называется весом дерева. Символы A,B,C,..., которые служат для обозначения вершин, называются метками вершин.

Слайд 5

Описание слайда:

A, B, C, D, K, L, M, N, R - метки вершин, вершина А - корень, вершины C, L, R, M, N, K - листья, вес дерева равен 6 (количество листьев - 6), вершина В имеет степень 2, вершина D имеет степень 4

Слайд 6

Описание слайда:

Определение 2 Вершина Y, которая находится непосредственно под узлом X, называется (непосредственным) потомком (сыном) X, вершина X в данном случае называется (непосредственным) предком (отцом) Y. В этом случае, если вершина X находится на уровне i, то говорят, что вершина Y находится на уровне i+1. Мы будем считать, что корень дерева расположен на уровне 0. Максимальный уровень какой-либо вершины дерева называется его глубиной или высотой. Максимальная степень всех вершин дерева называется степенью дерева.

Слайд 7

Описание слайда:

Следствия если вершина не имеет потомков, то она является листом; степень внутренней вершины можно определить как число ее (непосредственных) потомков.

Слайд 8

Описание слайда:

максимальное число вершин для дерева с высотой h и степенью d можно найти по формуле

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

Длина внутреннего пути = Длина внутреннего пути в левом поддереве + Длина внутреннего пути в правом поддереве + Количество узлов в дереве - 1.

Слайд 11

Описание слайда:

Определение 4 Лес - это множество деревьев (обычно упорядоченное), состоящее из некоторого (быть может, равного нулю) числа непересекающихся деревьев. Часто для леса, состоящего из n деревьев пользуются термином "дерево с n-кратным корнем".

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Определение 6 два бинарных дерева T и T' подобны, если они имеют одинаковую структуру; это означает, что подобные деревья либо оба пусты, либо оба непусты и их левые и правые поддеревья соответственно подобны. Попросту говоря, подобие означает, что графические изображения деревьев T и T' имеют одинаковую "конфигурацию".

Слайд 15

Описание слайда:

бинарные деревья T и T' эквивалентны, если они подобны и если, кроме того, соответствующие вершины содержат одинаковую информацию. Если Info (u) обозначает информацию, содержащуюся в вершине u, то формально деревья эквивалентны тогда и только тогда, когда они: либо оба пусты, либо же оба непусты, Info (Корень(T))=Info (Корень(T')) и их левые и правые поддеревья соответственно эквивалентны.

Слайд 16

Описание слайда:

Первые два из них не подобны; второе, третье и четвертое деревья подобны, причем второе и четвертое эквивалентны

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

struct node { int Key; // Ключ вершины. int Count; // Счетчик количества вершин с одинаковыми ключами. node *Left; // Указатель на "левого" сына. node *Right; // Указатель на "правого" сына. };

Слайд 19

Описание слайда:

Построение бинарного дерева поиска Tree - указатель на корень дерева p - вспомогательный указатель на вершину дерева

Слайд 20

Описание слайда:

Tree = NULL; //Построение пустого дерева p = new(node); (*p).Key = 100; (*p).Count = 1; (*p).Left = NULL; (*p).Right = NULL; Tree = p;

Слайд 21

Описание слайда:

p = new(node); (*p).Key = 50; (*p).Count = 1; (*p).Left = NULL; (*p).Right = NULL;

Слайд 22

Описание слайда:

(*Tree).Left = p;

Слайд 23

Описание слайда:

p = new(node); (*p).Key = 200; (*p).Count = 1; (*p).Left = NULL; (*p).Right = NULL;

Слайд 24

Описание слайда:

(*Tree).Right = p;

Слайд 25

Описание слайда:

(*Tree).Count = (*Tree).Count + 1;

Слайд 26

Описание слайда:

void BuildTree (node **Tree) // Построение бинарного дерева. // *Tree - указатель на корень дерева. { int el; *Tree = NULL; // Построено пустое бинарное дерево. coutel; while (el!=0) { Search (el,Tree); cin>>el;} }

Слайд 27

Описание слайда:

void Search (int x, node **p) void Search (int x, node **p) // Поиск вершины с ключом x в дереве со вставкой // (рекурсивный алгоритм). // *p - указатель на корень дерева. { if (*p==NULL) { // Вершины с ключом x в дереве нет; включить ее. *p = new(node); (**p).Key = x; (**p).Count = 1; (**p).Left = (**p).Right = NULL; } else //Поиск места включения вершины. if (x(**p).Key) //Включение в правое поддерево. Search (x,&((**p).Right)); else (**p).Count = (**p).Count + 1; }

Слайд 28

Описание слайда:

Анализ алгоpитма поиска с включениями Теоpема Хопкpофта-Ульмана Сpеднее число сpавнений, необходимых для вставки n случайных элементов в деpево поиска, пустое вначале, pавно O(nlog2n) для n>=1.

Слайд 29

Описание слайда:

Левосторонний обход бинарного дерева поиска A B D M N E C B D C E R посетите корень дерева; обойдите левое поддерево; обойдите правое поддерево.

Слайд 30

Описание слайда:

void ObhodLeft (node **w) // Левосторонний обход дерева. // *w - указатель на корень дерева. { if (*w!=NULL) { cout

Слайд 31

Описание слайда:

Концевой обход бинарного дерева поиска обойдите левое поддерево; обойдите правое поддерево; посетите корень дерева. M N D E B C A D E R C B

Слайд 32

Описание слайда:

void ObhodEnd (node **w) // Концевой обход дерева. // *w - указатель на корень дерева. { if (*w!=NULL) { ObhodEnd (&((**w).Left)); ObhodEnd (&((**w).Right)); cout

Слайд 33

Описание слайда:

Обратный обход бинарного дерева поиска обойдите левое поддерево; посетите корень дерева; обойдите правое поддерево. M D N B E A C D B E C R

Слайд 34

Описание слайда:

void ObhodBack (node **w) // Обратный обход бинарного дерева. // *w - указатель на корень дерева. { if (*w!=NULL) { ObhodBack (&((**w).Left)); cout

Слайд 35

Описание слайда:

Вывод бинарного дерева поиска void Vyvod (node **w,int l) // Изображение дерева w на экране дисплея. // (рекурсивный алгоритм). // *w - указатель на корень дерева. { int i; if (*w!=NULL) { Vyvod (&((**w).Right),l+1); for (i=1; i

Слайд 36

Описание слайда:

Построение бинарного дерева (нерекурсивный алгоритм) Tree = new(node); (*Tree).Right = NULL; p2 = Tree; p1 = (*p2).Right;

Слайд 37

Описание слайда:

p1 = new(node); (*p1).Key = Элем1; (*p1).Left = (*p1).Right = NULL; (*p1).Count = 1;

Слайд 38

Описание слайда:

void TreeSearch (node **Tree,int el) // Поиск вершины с информационным полем el в дереве // с последующим включением. // *Tree - указатель на корень дерева. { node *p1; node *p2; // Указатель p2 "опережает" указатель p1. int d; // Флаг для распознавания поддеревьев. p2 = *Tree; p1 = (*p2).Right; d = 1; // Флаг правого поддерева. while (p1!=NULL && d!=0) { p2 = p1; if (el(*p1).Key) { p1 = (*p1).Right; d = 1; } else d = 0; } if (d==0) (*p1).Count = (*p1).Count + 1; else { p1 = new(node); (*p1).Key = el; (*p1).Left = (*p1).Right = NULL; (*p1).Count = 1; if (d

Слайд 39

Описание слайда:

Изображение бинарного дерева (нерекурсивный алгоритм) struct no { no *sled; // Указатель на вершину. node *elem; // Информационное поле. int ch; // Уровень вершины. }