47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

84910. Проектирование локальной вычислительной сети 2.42 MB
  Спроектировать ЛВC, состоящую из пяти маршрутизаторов, составить таблицы маршрутизации для каждого из маршрутизаторов и для рабочих станций. Необходимо обеспечить наличие маршрута по умолчанию. Применить к спроектированной сети технологию VLAN.
84911. Планирование и организация технического обслуживания дорожных машин, автомобилей и тракторов с разработкой технического проведения первого технического обслуживания (ТО-1) экскаватора (на гусеничном ходу) 619.04 KB
  В настоящее время машинные парки дорожно-строительных организаций и дорожно-эксплуатационных хозяйств пополняются экскаваторами, автогрейдерами, бульдозерами, скреперами, катками, планировочно-уплотняющей техникой современных универсальных исполнений с гидроприводом...
84912. Краткосрочный прогноз речного стока с использованием системного математического моделирования 666.5 KB
  Псковская область расположена на северо-западе Восточно-Европейской (Русской) равнины. Рельеф преимущественно низменно-холмистый (средняя высота — 110 м над уровнем моря) с тремя явно выделяющимися возвышенностями: Лужская возвышенность на севере области с максимальной высотой 204 м (гора Кочебуж)...
84914. Производство с двумя переменными факторами производства. Предельная норма технологического замещения 158.69 KB
  Изокванты в производстве выполняют ту же функцию, что и кривые безразличия в потреблении, поэтому они подобны: на графике также имеют отрицательный наклон, обладают определенной пропорцией замещения факторов, не пересекаются между собой и чем дальше расположены от начала координат...
84915. Подземная разработка пластовых месторождений 4.57 MB
  Содержание задания: На основании горно-геологических характеристик и условий залегания месторождения определить технологические и технические параметры разработки месторождения или отдельных его участков. Исходные данные для выполнения курсового проекта: Протяженность шахтного поля по простиранию 4,5 км, по падению 4,0 - 5,0 км.
84916. Объектов конфигураций 1С:Предприятия 5.59 MB
  Встроенный язык программирования 1С: Предприятие — язык программирования, который используется в семействе программ «1С: Предприятие». Данный язык является предварительно компилируемым языком высокого уровня. Средой исполнения языка является программная платформа «1С: Предприятие».
84917. Совершенствование деятельности ЗАО «Грузовой терминал Пулково» 331.71 KB
  Воздушные авиаперевозки являются самым быстрым и одновременно наиболее дорогим способом доставки груза. Перевозка грузов воздушным транспортом позволяет существенно сократить общее время доставки груза и решает проблему транспортировки грузов практически в любое место на земном шаре.
84918. Расчет заземления 1.11 MB
  Значение безразмерного коэффициента F для газообразных вредных веществ и мелкодисперсных аэрозолей скорость упорядоченного оседания которых практически равна нулю принимают равным единице F = 1 для пыли и золы коэффициент F выбирают из условий: Степень очистки газа F выше 90 2 от 75 до 90 25 менее 75 3 Безразмерный коэффициент m определяют по формуле: где f – коэффициент м с2 оС определяемый по формуле: Коэффициент n определяется в зависимости от опасной скорости ветра Vм м с: при Vм 05 n = 44 Vм; при 05 ≤ Vм 2 n =...