Презентация Динамические структуры данных. Деревья онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Динамические структуры данных. Деревья абсолютно бесплатно. Урок-презентация на эту тему содержит всего 98 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:98 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:5.23 MB
- Просмотров:127
- Скачиваний:1
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Динамические структуры данных
Прикладное программирование
№2 слайд
Содержание слайда: Деревья – основные понятия
Связной граф без циклов называется деревом. Пример дерева приведен на рисунке.
№3 слайд
Содержание слайда: Деревья – основные понятия
Следующие определения дерева эквивалентны. Граф G=(V, E), где |V| =N и |E| =M является деревом, если:
G – связный граф и M=N-1;
G – ациклический граф и M=N-1;
любые две несовпадающие вершины графа G соединяет единственная простая цепь;
G – ациклический граф, обладающий тем свойством, что если какую-либо пару несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.
№4 слайд
Содержание слайда: Деревья – основные понятия
Терминология, связанная с понятием дерева:
корнем дерева называют единственную вершину, находящуюся вверху «перевернутого» дерева;
самые нижние вершины дерева называют листьями;
вершину называют внутренней, если она не является ни корнем и ни листом;
о вершине, которая находится непосредственно над другой вершиной, говорят, что она – родитель (предок), а вершина, которая расположена непосредственно под другой вершиной, называется потомком.
№5 слайд
Содержание слайда: Деревья – основные понятия
На рисунке вершина с номером 1 – корень; вершины с номерами 4, 5, 6, 9, 10, 11 – листья; вершины 2, 3, 7, 8 – внутренние; вершина 3- родитель вершины 7; вершина 8 – потомок вершины 3.
№6 слайд
Содержание слайда: Деревья – основные понятия
Считают, что корень дерева расположен на первом уровне. Его потомки находятся на втором уровне и т. д. Максимальный уровень какой-либо вершины дерева называется глубиной или высотой дерева. Число потомков вершины называется ее степенью. Максимальное значение этих степеней есть степень дерева. Степень дерева на рисунке, приведенном выше, равна трем.
№7 слайд
Содержание слайда: Деревья – основные понятия
Деревья в программировании используются значительно чаще, чем графы. Так, на построении деревьев основаны многие алгоритмы сортировки и поиска. Компиляторы в процессе перевода программы с языка высокого уровня на машинный язык представляют фрагменты программы в виде деревьев, которые называются синтаксическими.
№8 слайд
Содержание слайда: Деревья – основные понятия
Деревья естественно применять всюду, где имеются какие-либо иерархические структуры, т.е. структуры, которые могут вкладываться друг в друга. Примером может служить оглавление книги.
№9 слайд
Содержание слайда: Деревья – основные понятия
Суть двоичных деревьев, широко распространенных в программировании, следует из названия. Степень дерева равна двум. Вершина (узел) дерева может иметь не более двух потомков, их называют левыми и правыми.
№10 слайд
Содержание слайда: Деревья – основные понятия
Двоичные (бинарные) деревья поиска (подкласс двоичных деревьев) характеризуются тем, что значение информационного поля, связанного с вершиной дерева, больше любого соответствующего значения из левого поддерева и меньше, чем содержимое любого узла его правого поддерева.
№11 слайд
Содержание слайда: Описание двоичного дерева
struct node
{
int info; //Информационное поле
node *l, *r;//Левая и Правая часть дерева
};
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
№12 слайд
Содержание слайда: Вид двоичного дерева
№13 слайд
Содержание слайда: Вид двоичного дерева
Что же нам дает такое упорядочивание? То, что мы легко можем отыскать требуемый ключ x в дереве! Просто сравним x со значением в корне. Если они равны, то мы нашли требуемое. Если же x меньше (больше), то он может оказаться только в левом (соответственно правом) поддереве.
№14 слайд
Содержание слайда: Вид двоичного дерева
№15 слайд
Содержание слайда: Основные операции с деревом
Основные операции:
вставка элемента в дерево;
удаление элемента из дерева;
обход дерева.
№16 слайд
Содержание слайда: Добавление элемента в дерево
То, что указано в описании - это структура, описывающая звено дерева. По ходу выполнения программы Звенья будут создаваться и дописываться к существующим по указанным правилам. Сама эта структура – это фундамент очень простого бинарного дерева.
№17 слайд
Содержание слайда: Добавление элемента в дерево
Заполнение простого бинарного дерева разделено на три основные части, а именно – Если дерево пустое, то надо создать первый элемент. Этот элемент будет корнем дерева. После создания первого элемента надо выделить память для возможных ветвей.
Если дерево что-то содержит, то проверяется условие, согласно которому мы размещаем в дереве элементы.
№18 слайд
Содержание слайда: Добавление элемента в дерево
Бинарное дерево – это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
№19 слайд
Содержание слайда: Добавление элемента в дерево
При всем этом, если элемент, который мы хотим поместить в дерево больше чем корневой, то с помощью рекурсивного вызова функции происходит последовательное перемещение элемента в правую часть.
Если записываемый элемент меньше чем корневой, то выполняется такая же перестановка, только в левую сторону.
№20 слайд
Содержание слайда: Добавление элемента в дерево
№21 слайд
Содержание слайда: Добавление элемента в дерево
void add_node(int x, Node *&MyTree) //Функция добавления звена в дерево
{
if (NULL==MyTree) //Если дерева нет, то добавляем первый корневой элемент
{
MyTree=new Node; //Выделяем память под звено дерева
№22 слайд
Содержание слайда: Добавление элемента в дерево
MyTree->x=x; //Записываем данные в звено
MyTree->l=MyTree->r=NULL; //Подзвенья инициализируем пустотой во избежание ошибок
}
}
№23 слайд
Содержание слайда: Добавление элемента в дерево
if (x<MyTree->x) //Если нововведенный элемент x меньше чем элемент x из корня дерева, уходим влево
{ if (MyTree->l!=NULL) add_node(x, MyTree->l); //При помощи рекурсии помещаем элемент на свободный участок
else //Если элемент получил свой участок, то
{ MyTree->l=new Node; //Выделяем память левому подзвену.
№24 слайд
Содержание слайда: Добавление элемента в дерево
MyTree->l->l=MyTree->l->r=NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой
MyTree->l->x=x; //Записываем в левое подзвено записываемый элемент
}
}
№25 слайд
Содержание слайда: Добавление элемента в дерево
if (x>MyTree->x) //Если нововведенный элемент x больше чем элемент x из корня дерева, уходим вправо
{ if (MyTree->r!=NULL) add_node(x, MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок
else //Если элемент получил свой участок, то
{ MyTree->r=new Node; //Выделяем память правому подзвену.
№26 слайд
Содержание слайда: Добавление элемента в дерево
MyTree->r->l=MyTree->r->r=NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой
MyTree->r->x=x; //Записываем в правое подзвено записываемый элемент
}
}
}
№27 слайд
Содержание слайда: Обход дерева
void show(Node *&Tree) //Функция обхода
{
if (Tree!=NULL) //Пока не встретится пустое звено
{
show(Tree->l); //Рекурсивная функция для вывода левого поддерева
cout<<Tree->x; //Отображаем корень дерева
show(Tree->r); //Рекурсивная функци для вывода правого поддерева
}
}
№28 слайд
Содержание слайда: Удаление элемента из дерева
Реализация удаления элемента из дерева чуть сложнее. Если узел имеет одного потомка, то в поле ссылки родителя удаляемого элемента записывается ссылка, не равная NULL, и на этом все закончено.
№29 слайд
Содержание слайда: Удаление элемента из дерева
В том случае, когда у удаляемого элемента два потомка, для сохранения структуры дерева поиска на место этого элемента необходимо записать или самый правый элемент левого поддерева, или самый левый элемент правого поддерева.
№30 слайд
Содержание слайда: Удаление элемента из дерева
№31 слайд
Содержание слайда: Удаление элемента из дерева
№32 слайд
Содержание слайда: Удаление элемента из дерева
№33 слайд
Содержание слайда: Удаление элемента из дерева
Тут так просто не получится — у левого потомка может уже быть правый потомок. Поступим по-другому: найдем в правом поддереве минимум. Ясно, что его можно найти если начать в правом потомке и идти до упора влево. Т.к у найденного минимума нет левого потомка, можно вырезать его по аналогии со случаем 1 и вставить его вместо удаляемой вершины. Из-за того что он был минимальным в правом поддереве, свойство упорядоченности не нарушится:
№34 слайд
Содержание слайда: Удаление элемента из дерева
№35 слайд
Содержание слайда: Удаление элемента из дерева
//ищем самую правую вершину левого поддерева
void del_potomka(struct BinaryTree *r, struct BinaryTree *q) //в качестве аргумента элемент, который и надо удалить
{
if(r->right!=NULL) del_potomka(r->right, q);
else
{
q->data=r->data;
q=r;
r=r->left;
}
}
№36 слайд
Содержание слайда: Удаление элемента из дерева
/*удаление вершины из дерева*/
void delete_element(int x, struct BinaryTree *p)
{
if(p==NULL) printf("Элемента в дереве нет!\n");
else if(x<p->data) delete_element(x,p->left); //идём влево
else if(x>p->data) delete_element(x,p->right); //идём вправо
№37 слайд
Содержание слайда: Удаление элемента из дерева
else //исключаем элемент
{
struct BinaryTree *q=p;
if(q->right==NULL) p=q->left;//если нет правого потомка
else if(q->left==NULL) p=q->right; //если нет левого потомка
else del_potomka(q->left, q);//если у нас 2 потомка
free(q);
}
№38 слайд
Содержание слайда:
№39 слайд
Содержание слайда:
№40 слайд
Содержание слайда:
№41 слайд
Содержание слайда:
№42 слайд
Содержание слайда:
№43 слайд
Содержание слайда:
№44 слайд
Содержание слайда:
№45 слайд
Содержание слайда:
№46 слайд
Содержание слайда:
№47 слайд
Содержание слайда:
№48 слайд
Содержание слайда:
№49 слайд
Содержание слайда:
№50 слайд
Содержание слайда:
№51 слайд
Содержание слайда:
№52 слайд
Содержание слайда:
№53 слайд
Содержание слайда:
№54 слайд
Содержание слайда:
№55 слайд
Содержание слайда: .
№56 слайд
Содержание слайда:
№57 слайд
Содержание слайда:
№58 слайд
Содержание слайда:
№59 слайд
Содержание слайда:
№60 слайд
Содержание слайда:
№61 слайд
Содержание слайда:
№62 слайд
Содержание слайда:
№63 слайд
Содержание слайда:
№64 слайд
Содержание слайда:
№65 слайд
Содержание слайда:
№66 слайд
Содержание слайда:
№67 слайд
Содержание слайда:
№68 слайд
Содержание слайда:
№69 слайд
Содержание слайда:
№70 слайд
Содержание слайда:
№71 слайд
Содержание слайда:
№72 слайд
Содержание слайда:
№73 слайд
Содержание слайда:
№74 слайд
Содержание слайда:
№75 слайд
Содержание слайда:
№76 слайд
Содержание слайда:
№77 слайд
Содержание слайда:
№78 слайд
Содержание слайда:
№79 слайд
Содержание слайда:
№80 слайд
Содержание слайда:
№81 слайд
Содержание слайда:
№82 слайд
Содержание слайда:
№83 слайд
Содержание слайда:
№84 слайд
Содержание слайда:
№85 слайд
Содержание слайда:
№86 слайд
Содержание слайда:
№87 слайд
Содержание слайда:
№88 слайд
Содержание слайда:
№89 слайд
Содержание слайда:
№90 слайд
Содержание слайда:
№91 слайд
Содержание слайда:
№92 слайд
Содержание слайда:
№93 слайд
Содержание слайда:
№94 слайд
Содержание слайда:
№95 слайд
Содержание слайда:
№96 слайд
Содержание слайда:
№97 слайд
Содержание слайда:
№98 слайд
Содержание слайда:
Скачать все slide презентации Динамические структуры данных. Деревья одним архивом:
