47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

37355. Средства и технологии разработки приложений Windows CGI 91.1 KB
  Протокол CGI - Common Gateway Interface служит для связи веб-сервера с другими программами. На его основе работают гостевые книги, форумы, интернет-магазины и любые другие интерактивные сайты. Заполняя HTML-форму на сайте, нажимая кнопку Отправить, после чего обозреватель передает данные веб-серверу
37356. Основний навчально-програмний матеріал з філософії 48.5 KB
  Періодизація античної давньогрецької і давньоримської філософії. Підперіоди античної філософії. Головний зміст досократичної філософії.
37357. ВАЛЕОЛОГИЯ КУРС ЛЕКЦИЙ 2.88 MB
  Это стиль и право автора преподносить информацию в таком виде Высокий профессионализм автора имеющего медицинское психологическое и педагогическое образование позволил осветить избранный круг вопросов по здоровому образу жизни медикосоциальным психологическим и юридическим аспектам долголетия сердечнососудистым заболеваниям алкоголизму абортам двигательной активности и другим социально значимым вопросам. Надеюсь что студенты и преподаватели педагогических вузов колледжей и лицеев с гуманитарным уклоном а также многочисленные...
37358. Общие требования и порядок выполнения курсовой работы 339 KB
  Что оценивает научный руководитель в твоей курсовой работе При оценке работы учитывается актуальность степень самостоятельности качество проведенного лингвистического анализа уровень общей и профессиональной грамотности. Работа над курсовым исследованием Нужно знать что работа над курсовым исследованием состоит из нескольких этапов: формирование замысла работы определение объекта и предмета исследования цели работы; поиск и обработка специальной литературы по проблеме исследования; отбор и подготовка фактического материала;...
37359. Упаковка и брендинг продукта: шоколад 5.99 MB
  Бренд - известная торговая марка, окружённая набором ожиданий, ассоциированных с продуктом или услугой, которые типично возникают у людей. Создание бренда (брендинг) - один из самых важных этапов формирования потребительской аудитории товара, продукта или услуги.
37362. История отечественного государства и права. Часть 2 2.61 MB
  ПРИНЯТЫЕ СОКРАЩЕНИЯ ВВС РСФСР Ведомости Верховного Совета Российской Советской Федеративной Социалистической Республики ВВС СССР Ведомости Верховного Совета Союза Советских Социалистических Республик ВСНД РСФСР Ведомости Съезда народных депутатов РСФСР и Верховного Совета и ВС РСФСР РСФСР ВСНД РФ Ведомости Съезда народных депутатов Российской Федерации и и ВС РФ Верховного Совета Российской...
37363. Разработка программного обеспечения решения задачи о назначении сотрудников на должности 199.52 KB
  Имеется конечное число видов работ, которые могут быть выполнены потенциальными кандидатами на эти должности. При этом каждого кандидата можно назначить на выполнение только одной работы, а каждая работа, в свою очередь, должна выполняться только одним кандидатом. Известна эффективность выполнения каждой работы (или издержки при назначении) любым из потенциальных кандидатов.