47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

48115. Соціологія як наука. Предмет, структура і функції соціології 1.46 MB
  Наявність спільних проблем дослідження інтереси соціальні установки та цінності орієнтації думки настрої людей. Нині переважаючою стає тенденція до комплексного всебічного дослідження явищ і процесів суспільного життя до спільного дослідження з точки зору декількох наук до комбінування поєднання їх пізнавальних можливостей. Дослідження соціальної структури суспільства і вироблення поняття соціальна стратифікація як постійної характеристики будьякого організованого суспільства. Перенесення акцентів на дослідження систем держав з...
48116. Культура фахового мовлення. Навчальний посібник 792 KB
  Черкаси ЧДТУ 2010 ПЕРЕДМОВА Оскільки мова використовується в усіх сферах сучасного суспільного життя то майбутні фахівці з гуманітарних і негуманітарних спеціальностей мають досконало знати державну мову вільно володіти лексичним і фразеологічним багатством української літературної мови розуміти норми орфоепії орфографії граматики стилістики та вміти застосовувати їх на практиці. Метою пропонованого посібника є підвищення загальномовного рівня студентів ознайомлення з особливостями ділової української мови офіційноділового стилю їх...
48118. Корреляционно–регрессионный анализ связей социально–экономических явлений 405 KB
  В среднем по совокупности 20 9525 ПОЛЕ КОРРЕЛЯЦИИ Рисунок 3 Зависимость производственной себестоимости 1 ц зерна от объема ЭМПИРИЧЕСКАЯ ЛИНИЯ РЕГРЕССИИ Рисунок 4 Зависимость уровня заработной платы рабочих сельскохозяйственных предприятий региона от производительного стажа их работы ПОКАЗАТЕЛИ ТЕСНОТЫ СВЯЗИ 1 Коэффициент корреляции знаков Фехнера: где nа число совпадений знаков отклонений индивидуальных значений признаков от их среднего значения; nв число несовпадений...
48119. Показатели вариации и анализ вариационных рядов 244.5 KB
  Ширина интервала Число кредитных организаций Плотность распределения до 3 3 150 50 3 10 7 254 363 10 30 20 316 158 30 60 30 256 85 60 150 90 144 16 150300 150 90 06 300 и выше 150 112 07 Итого 1322 ПОКАЗАТЕЛИ ЦЕНТРА РАСПРЕДЕЛЕНИЯ Средняя арифметическая для дискретного ряда распределения: где варианты значений признака; частота повторения данного варианта. Средняя арифметическая для интервального ряда распределения: где середина соответствующего интервала; частота или частость ряда. 1 ...
48120. Основы алгоритмизации. Основы программирования 2.4 MB
  Для ввода данных в компьютер используется: клавиатура набор данных вручную; жесткий диск ввод данных из файла. Для вывода данных из компьютера используется: экран монитора для визуализации; принтер для документирования; жесткий диск для сохранения данных в файле. Алгоритм как вычислительный процесс это точное предписание определяющее вычислительный процесс ведущий от варьируемых исходных данных к искомому результату рис. Определенность предписания алгоритма должны быть точными и понятными обеспечивать...
48121. РЯДЫ ДИНАМИКИ 514.5 KB
  Виды рядов динамики Таблица 1 Показатели размера крестьянских фермерских хозяйств в Тамбовской области в 20032007 годы Показатели Вид ряда 2003 г. 1594 104 843 802 691 649 Приемы приведения уровней динамического ряда к сопоставимому виду: смыкание рядов динамики; приведение уровней к одному основанию; приведение сравниваемых показателей к однородной структуре; замена абсолютных показателей относительными; приведение...
48122. СТАТИСТИЧЕСКИЕ ТАБЛИЦЫ И ГРАФИКИ 319.5 KB
  ПЕРЕЧНЕВАЯ ТАБЛИЦА ПО ВИДОВОМУ ПРИЗНАКУ Таблица 2 Ресурсы ФГУП учхозплемзавода Комсомолец Мичуринского района Тамбовской области. ПЕРЕЧНЕВАЯ ТАБЛИЦА ПО ТЕРРИТОРИАЛЬНОМУ ПРИЗНАКУ Таблица 3 Потребление основных продуктов питания населением областей ЦентральноЧернозёмного района в 2010 году на душу населения; килограммов Область Мясо и мясопродукты Молоко и молокопродукты Хлебные продукты Фрукты и ягоды Белгородская 62 249 140 46...
48123. Статистические показатели 155.5 KB
  Индивидуальные значения признака частота повторения значений признака в совокупности весы Методика расчёта различных видов степенных средних величин Вид степенной средней Показатель степени Формула расчёта простая взвешенная Средняя гармоническая 1 Средняя геометрическая 0 Средняя арифметическая 1 Средняя квадратическая 2 ПРАВИЛО МАЖОРАНТНОСТИ СРЕДНИХ СВОЙСТВА СРЕДНЕЙ АРИФМЕТИЧЕСКОЙ ВЕЛИЧИНЫ средняя арифметическая постоянной величины равна этой постоянной: нулевое алгебраическая сумма линейных отклонений...