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

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

Содержание ▲

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

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

Слайд 1

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

ДЕРЕВЬЯ Деревья представляют собой иерархическую структуру некой совокупности элементов.

Слайд 2

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

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

Слайд 3

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

Будем определять дерево как конечное множество Т, состоящее из одного или более узлов, таких, что: имеется один специально обозначенный узел, называемый корнем данного дерева; остальные узлы (исключая корень) содержатся в попарно не пересекающихся множествах Т1 , Т2 , … , Тn , каждое из которых в свою очередь является деревом. Деревья Т1 , Т2 , … , Тn называются поддеревьями данного корня. Это определение является рекурсивным, т.е. мы определили дерево в терминах самих же деревьев.

Слайд 4

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

Каждый узел дерева является корнем некоторого поддерева, которое содержится в этом дереве. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется листом.

Слайд 5

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

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

Слайд 6

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

Примеры Дерево двоичного поиска

Слайд 7

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

На C++ бинарное дерево можно представить следующим образом: struct tree { int inf; tree *left, *right; }; tree *root; В таком представлении дерево определяется указателем на свой корень. Каждый узел содержит информационную часть (inf) и указатели на узлы, которые являются его левым (left) и правым (right) сыном.

Слайд 8

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

Обходы бинарных деревьев Обойти дерево – это побывать в каждом из его узлов точно по одному разу. Рассмотрим три наиболее часто используемых способов обхода бинарных деревьев – это обход в прямом, симметричном и обратном порядке. Все три обхода будем определять рекурсивно. а) Прямой обход: попасть в корень; пройти левое поддерево данного корня; пройти правое поддерево данного корня. Подпрограмму, составляющую список узлов дерева при прохождении его в прямом порядке, можно записать следующим образом: void preorder (tree *root) { if (root) { cout

Слайд 9

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

б) Симметричный обход: пройти левое поддерево данного корня; попасть в корень; пройти правое поддерево данного корня. Подпрограмму, составляющую список узлов дерева при прохождении его в симметричном порядке, можно записать следующим образом: void inorder (tree *root) { if (root) { inorder(root->left); cout

Слайд 10

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

в) Обратный обход: пройти левое поддерево данного корня; пройти правое поддерево данного корня; попасть в корень. Подпрограмму, составляющую список узлов дерева при прохождении его в обратном порядке, можно записать следующим образом: void postorder (tree *root) { if (root) { postorder(root->left); postorder(root->right); cout

Слайд 11

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

Операции с деревьями бинарного поиска: Построение дерева Рассмотрим подпрограмму add (int x, tree *&root), которая добавляет новый узел в дерево так, что бы формировалось дерево бинарного поиска. Она имеет два формальных параметра: x – информация, которая записывается в новый узел; root – указатель на текущий узел дерева (вначале на корень исходного дерева).

Слайд 12

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

Построение дерева бинарного поиска void add (int x, tree *&root) { if (!root) { root = new tree; root->inf = x; root->left = root->right = NULL; } else if (x < root->inf) add(x, root->left); else if (x > root->inf) add(x, root->right); } Для формирования дерева в основной программе можно написать обращение к этой подпрограмме на этапе ввода в цикле узлы дерева с клавиатуры или считывания их из файла.

Слайд 13

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

Поиск по дереву Рассмотрим подпрограмму search (int x, tree *root), предназначенную для поиска и вывода данного узла. Подпрограмма имеет два формальных параметра: x – значение, которое нужно найти; root – указатель на анализируемый узел (вначале root указывает на корень дерева).

Слайд 14

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

Поиск по дереву void search (int x, tree *root) { if (!root) coutleft); else if (x > root->inf) search(x, root->right); else cout

Слайд 15

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

Операции с идеально сбалансированными деревьями Построение дерева Рассмотрим подпрограмму create (int number, tree *&root), которая используется для формирования идеально сбалансированного дерева. number – количество узлов в формируемом дереве; root – указатель на корень дерева. Необходимо выполнить требование: для каждого узла количество узлов в левом поддереве отличается от количества узлов в правом поддереве не больше чем на единицу. Первый узел полагается корнем формируемого дерева, после чего определяется количество узлов в левом поддереве numberLeft = number/2, количество узлов в правом поддереве numberRight = number- numberLeft -1.

Слайд 16

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

Построение идеально сбалансированного дерева void create (int number, tree *&root) { int a; if (number > 0) { root = new tree; in >> a; //считываем из файла in очередное число root->inf = a; root->left = root->right = NULL; int numberLeft = number/2, numberRight = number – numberLeft - 1; create(numberLeft, root->left); create(numberRight, root->right); } }

Слайд 17

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

Поиск по дереву Для реализации поиска элемента в идеально сбалансированном дереве можно использовать модификацию любого вида обхода дерева. Модификация прямого обхода: void search (int x, tree *root) {if (root) // если дерево не пустое if (x == root->inf) /* и значение узла равно x, то выводим сообщение об успешности поиска и выходим из подпрограммы */ { cout left); /* иначе обходим левое и правое поддеревья */ search(x, root->right); } }