47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

43055. Разработка предложений по созданию логистической системы 353.5 KB
  Считается, что анализируемые грузопотоки характеризуются стабильностью на проектную перспективу. Основной показатель, на который мы будем ориентироваться в ходе выполнения курсовой работы – это суммарные расходы на перевозку груза, которые зависят от количества перевозимого груза, расстояния перевозки и грузоподъемности подвижного состава, а также тарифа на перевозку.
43057. Разработка предложений по созданию логистической системы 319.93 KB
  Выбор и обоснование типа автотранспортного средства.1 Поставщики № поставщика Поставщик 51 Полтава 54 Карловка полтавса 61 Донецк 67 Красноармейск донец 83 ВолодарскВолынский житомир 85 Черняхов житомир 87 Городница житомио 114 Городище луганс 200 Монастыриска тернопол 350 Курджиново краснодар Порты отправления: Ейск Херсон Керчь. т Стоимость транспортировки 1т за 1км: С1км = 05 ден. Общая характеристика проектной ситуации Транспортная характеристика груза Стекло в ящиках витринное: Твердый прозрачный хрупкий материал получаемый...
43058. Разработка информационной системы по учёту продукции сети аптек 1001.5 KB
  Результаты дипломной работы – программное средство, с помощью которого можно вести учет продукции, оно является Windows – приложением и имеет удобный интерфейс. Программное средство даёт возможность просматривать данные, добавлять новые данные, изменять и удалять существующие данные, а также осуществлять поиск по таблицам.
43059. Проект электродинамического громкоговорителя 601 KB
  Для этого по графику зависимости (xm) (рис.2) находим минимальное допустимое, при заданной амплитуде смещения xm, значение ширины свободного воздушного зазора bз, от размера которого зависит скорость теплообмена и допустимая удельная мощность, которая рассеивается единицей поверхности. Величину Руд находим по графику зависимости Руд() (рис.3).
43060. МЕНЕДЖМЕНТ ПРОФЕСІЙНОЇ ДІЯЛЬНОСТІ 197.5 KB
  5 Методичні вказівки з виконання курсової роботи в межах курсу Менеджмент професійної діяльності для студентів спеціальностей напрямку підготовки 8. В процесі виконання курсової роботи керівником проектування здійснюються індивідуальні і групові консультації. Методичні вказівки З виконаннЯ курсової роботи 4.
43061. Основи менеджменту. Методичні вказівки 263 KB
  У роботі передбачається що студент уважно розгляне зовнішні і внутрішні чинники що впливають на діяльність організації і з урахуванням особливостей моменту буде використовувати розглянуті теоретичні положення. Загальний аналіз діяльності конкретної організації. Опис організації і її продукту. Бачення майбутнього організації.
43062. Модернизация привода главного движения универсального токарно-винторезного станка модели 1М63 2.8 MB
  Станок универсальный токарно-винторезный модели 1М63 предназначен для выполнения самых разнообразных токарных работ, в том числе точения конусов и нарезания резьб метрической, дюймовой, модульной и питчевой.
43063. Расчет аппарата гашения извести в производстве известкового молока на ОАО «АВИСМА» 319 KB
  Гашение извести протекает по реакции: CO H2O = COH2 1593 ккал. Вместе с тем следует избегать и переохлаждения гасящейся извести так как оно может значительно замедлить процесс гашения извести. С ростом температуры выделившийся гидрат окиси кальция выпадает в осадок и обволакивает поверхность кусков негашеной извести.