47263

Процедура построения полного дерева поиска и ее особенности

Доклад

Исторические личности и представители мировой культуры

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

Русский

2014-03-31

20.87 KB

2 чел.

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

Эти подмножества называются левым и правым поддеревьями исходного дерева.

Каждый элемент бинарного дерева называется узлом дерева.

Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые левое и правое поддеревья

ДРУГИМИ СЛОВАМИ Полным бинарным деревом называется такое дерево, в котором каждая вершина имеет не более двух "сыновей", а заполнение вершин осуществляется впорядке отверхних уровней к нижним, причем на одном уровне заполнение вершин производится слева направо.

 

a) полное бинарное дерево; b) неполное бинарное дерево

На рисунке a) изображено полное бинарное дерево, которое имеет три уровня. На втором уровне находится только одна заполненная вершина (a), которая называется корневой. На первом уровне заполнены две вершины (б,в), на нулевом уровне заполнена одна (г). Дерево b) не является полным бинарным деревом, так как заполнение вершин уровня 0 осуществлялось не слева направо (не заполнена вершина между вершинами "г" и "д"). Нетрудно убедиться, что в дерево a) можно добавить (заполнить) максимум три вершины, чтобы количество уровней в нем не изменилось. Если мы добавим (заполним) четыре вершины, то получится полное четырехуровневое бинарное дерево, которое изображено на рисунке:

Полное четырехуровневое бинарное дерево.

Очевидно, что минимальное количество вершин в полном трехуровневом бинарном дереве равно 4, а максимальное в полностью заполненном – 7.


 

А также другие работы, которые могут Вас заинтересовать

4879. Сравнение эффективности алгоритмов сортировки 47.5 KB
  Сравнение эффективности алгоритмов сортировки. Каждый из рассмотренных алгоритмов сортировки обладает определенными преимуществами и недостатками. Для того, чтобы сравнивать между собой разные алгоритмы, необходимо сформулировать критерии, характери...
4880. Область видимости и время жизни переменных. Локальные и глобальные переменные. Статические переменные 49 KB
  Область видимости и время жизни переменных. Локальные и глобальные переменные. Статические переменные. Каждое имя в программе на С++ должно относиться к уникальной сущности –объекту, функции, типу или шаблону. Однако, это не означает, что оно м...
4881. Указатели на функции. Перегрузка функций. Шаблоны функций 61 KB
  Указатели на функции. Перегрузка функций. Шаблоны функций. Предположим, что нужно реализовать функцию сортировки массива строк с примерно таким прототипом: void sort( char beg, char end ) здесь beg и end являются указателями на начало и конец...
4882. Статические и динамические библиотеки 200.5 KB
  Статические и динамические библиотеки. Библиотеками называют сборники подпрограмм или объектов, как правило, ориентированных на решение набора близких по тематике задач. С точки зрения их организации и использования библиотеки бывают статическими ...
4883. Кодирование данных. Алгоритм Base64 41.5 KB
  Кодирование данных. Алгоритм Base64. Под кодом понимают определенную систему условных обозначений или сигналов, а процесс кодирования – это переход от одной формы представления информации к другой. При этом целью кодирования, как правило,...
4884. Структуры и объединения. Перечисления. Поиск и сортировка в массивах структур 57.5 KB
  Структуры и объединения. Перечисления. Поиск и сортировка в массивах структур. Подобно тому, как массив является совокупностью элементов одного типа, структуры в С++ представляют собой совокупность элементов произвольных типов, например: struct Stud...
4885. Связный список. Сортировка списков 51 KB
  Связный список. Сортировка списков. Как известно, массив всегда занимает непрерывный блок памяти, что позволяет быстро получать доступ к произвольному элементу массива по индексу, однако существенно затрудняет вставку и удаление элементов, поскольку...
4886. Многофайловые проекты. Средства отладки и тестирования 67 KB
  Многофайловые проекты. Средства отладки и тестирования. При программировании любых более-менее сложных задач неизбежно возникают проблемы, связанные с разрастанием исходного кода и вызываемыми этим неудобствами при разработке и отладке. Естественным...
4887. Обработка исключений и аномальных ситуаций в программировании 43.5 KB
  Обработка исключений. Исключением называют возникновение аномальной ситуации во время выполнения, которое программа может обнаружить, например: деление на 0, выход за границы массива или отсутствие требуемого количества свободной памяти. Такие сит...