47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

30047. Древовидные (иерархические) структуры данных в реляционных базах данных 1006.5 KB
  Сегодня большинство хранилищ данных как простых так и сложных построены на основе реляционных баз данных. Реляционные базы данных в большинстве случаев удовлетворяют требования какойлибо предметной области данных но часты и случаи когда требуется представление и хранение данных в иерархическом виде. Это снизит защищенность данных но избавит нас от долгих раздумий в самом начале пути.
30048. База данных пользователей сети 318.5 KB
  Далее в пояснительной записке прилагается подробное описание этапов создания автоматизированной информационной системы полное описание постановки задачи графический интерфейс программы и листинг полученной программы. Общий интерфейс АИС Рисунок 5 Форма: баланс Рисунок 6 форма: конфигурация сети Рисунок 7 Отчет Приложение 2 Листинги запросов Запрос1: CLOSE ALL use CLEAR PUBLIC q input ' Введите номр модема ' to q select distinct a. Лист № докум. Подпись Дата Лист 2 681.
30049. Решить дифференциальное уравнение с заданными начальными значениями 127.71 KB
  Данное уравнение необходимо решить методом Эйлера и Эйлера модифицированного а также сравнить результаты и сделать вывод об эффективности методов построить их графики.Метод Эйлера Данный метод одношаговый. Обобщим формулу для решения дифференциальных уравнений методом Эйлера: у х у 3.Эйлер модифицированный Для уменьшения погрешности вычислений часто используется модифицированный метод Эйлера.
30050. ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА 203.5 KB
  Торопова ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА Методические указания по выполнению курсовой работы для специальностей 210406. Методические указания по выполнению курсовой работы по дисциплине Вычислительная техника предназначены для студентов специальностей 210406. Методические указания содержат организацию выполнения курсовой работы индивидуальные задания курсовой работы методические указания по выполнению курсовой работы и литературу. Рекомендовано НМС УрТИСИ ГОУ ВПО СибГУТИ в качестве методических указаний по выполнению курсовой работы студентами...
30051. Решить задачу Коши для дифференциального уравнения 1-ого порядка 332.5 KB
  В работе необходимо решить задачу Коши для дифференциального уравнения 1-ого порядка на отрезке [x0, xk] с шагом h и начальным условием y (x0 )=y0 Дано дифференциальное уравнение:
30052. Визуализация численных методов 588 KB
  Поэтому численные методы решения дифференциальных уравнений играют важную роль в практике инженерных расчетов. Курсовая работа должно состоять из: программы написанной в Visual Basic которая решает дифференциальное уравнение и выводит решения уравнения полученные методом Эйлера модифицированного и методом РунгеКутта четвёртого порядка точности. И визуализирует их на графике в виде линий кривой прямой; пояснительной записки которая описывает методы решения и программу. Результаты решения предоставить в виде таблицы.
30053. Инвестиции в Российской экономике 285.88 KB
  Объектом данной работы являются инвестиции и инвестиционная деятельность, а конкретно инвестирование в основной капитал, а субъектом - инвестиции и инвестиционный климат в РФ, главным образом инвестиции в основной капитал