47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

81931. Управління формуванням попиту і стимулюванням збуту на підприємстві 868 KB
  Актуальність обраної теми дипломної роботи безперечна, оскільки управління збутом товарів промислового призначення включає рух матеріальних цінностей від підприємств виготівників, так і стрічний потік товарів. Разом з цим воно охоплює рух товарів до державних організацій...
81932. Товарознавча оцінка взуття, правила та порядок його переміщення через митний кордон України 282.32 KB
  Система регулювання зовнішньоекономічної діяльності України за роки становлення зазнала певних еволюційних змін, що зумовлені розвитком економіки країни в цілому. В період до перебудови, тобто за радянських часів, економіка носила автаркічний (закритий) характер.
81933. Тактика організації охорони громадського порядку органами внутрішніх справ в сучасних умовах 101.42 KB
  В умовах становлення та розвитку демократичної правової держави боротьба зі злочинністю розглядається як важлива сфера внутрішньої політики держави. Залучення державних органів, суспільних об’єднань і населення до охорони громадського порядку, а також профілактика правопорушень...
81934. Технологія виконання дизайну нігтів в манікюрі та педикюрі під креативний образ жінки 12.44 MB
  Одним із популярних дизайнів нігтів є французький манікюр. Так він називається тому, що був винайдений дизайнерами Франції. Він зразу ж знайшов популярність - як у жінок середніх шарів, так і біля зірок кіно і естради - за свою практичність і універсальність.
81935. Інвентаризаційна робота – об’єкт ревізійного дослідження 1.62 MB
  Проведення інвентаризації дозволяє підтвердити або спростувати інформацію тих бухгалтерських документів первинних та зведених по яких можна визначити законність доцільність і необхідність здійснених працівниками підприємства господарських операцій.
81936. Теоретичні та практичні аспекти вдосконалення організації праці та виробництва на прикладі місцевого підприємства 3.22 MB
  Важливою ознакою НОП є її спрямованість на рішення взаємозалежних груп завдань: економічних економія ресурсів підвищення якості продукції ріст результативності виробництва; психофізіологічних оздоровлення виробничого середовища гармонізація психофізіологічних навантажень на людину зниження ваги...
81937. Проблема профессионального самоопределения молодежи в условиях начального профессионального образования 537.5 KB
  В отечественной психологии накоплен богатый опыт в области теории профессионального самоопределения, который во многом предопределил современные подходы к данной проблеме. Это ставшими классическими исследования в области профессиональной ориентации и профконсультирования...
81938. Монтаж главных распределительных щитов (ГРЩ) 798.5 KB
  Щиты ГРЩ предназначены для приёма и распределения электроэнергии (возможен также учёт) в сетях переменного тока с разделенной землёй и нейтралью возможно подключение к сетям с глухозаземлённой нейтралью тип заземления TN-C, TN-S, TN-C-S напряжением до 380 вольт частотой 50 Гц...
81939. Особенности начисления заработной платы в бюджетном учреждении (на примере ФГУ «Карабашская КЭЧ района») 62.03 KB
  Учет труда и заработной платы по праву занимает одно из центральных мест во всей системе учета в учреждении. Он должен обеспечить оперативный контроль над количеством и качеством труда за использованием средств включаемых в фонд заработной платы и выплаты социального характера.