47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

4590. Повышение эффективности разработки Приобского месторождения за счет оптимального подбора параметров работы электропогружных установок 3.05 MB
  Погруженные центробежные насосы (УЭЦН) в настоящее время являются одним из основных средств механизированной эксплуатации нефтяных скважин. На их долю приходится более 53% добываемой в России нефти и более 63% извлекаемой из скважин жидкости...
4591. Уточнения должностных функций, выполняемых менеджером по обучению персонала на предприятии ООО Техно-регион 183.99 KB
  Введение Развитие персонала является важнейшим условием успешного функционирования любой организации. Это особенно справедливо в современных условиях, когда ускорение научно-технического прогресса значительно убыстряет процесс устаревания профессион...
4592. Диссертация магистранта, аспиранта, докторанта 3.27 MB
  Настоящее пособие дает представление о специфике и месте диссертации магистранта, аспиранта и докторанта в системе научного исследования. В нем выделены этапы исследования, для каждого из которых разработаны ментальные карты, чем пособие выгодно отл...
4593. Особенности функционирования молодежных субкультур России XXI века 4.04 MB
  Введение Актуальность темы исследования. Актуальность изучения проблем становления и развития культуры молодежи как самой активной и быстро реагирующей на любые перемены социально-демографической группы общества определяется происходящими социокульт...
4595. Модернизировать координатную ось динамической подвижной лазерной головки 6.26 MB
  Объектом разработки является модернизация координатной оси динамической подвижной оптической лазерной головки станка с ЧПУ, для расчёта оптимального способа обработки. Цель работы: Модернизировать координатную ось динамической подвижной лазерной гол...
4596. Организация пригородного движения на отделении дороги 2.62 MB
  Транспорт России – важная составная часть народного хозяйства. От его деятельности зависит развитие и функционирование предприятий, промышленности, сельского хозяйства, снабжения, торговли. Основная задача транспорта – полное и св...
4597. Принятие решений в условиях неопределенности. Игры с природой 129.5 KB
  Принятие решений в условиях неопределенности. Игры с природой Цель работы: освоить и закрепить практические навыки по принятию и обоснованию управленческих решений в условиях недостатка информации, когда один из игроков не имеет конкретной цели и сл...
4598. Основы программирования и алгоритмические языки. Конспект лекций 211.5 KB
  Лекция 1. Введение в язык java История возникновения языка Java Язык Java является одним из самых молодых языков программирования. Он моложе таких популярных языков, как Basic, Pascal, С и С++. Поскольку в момент создания Java язык С++ являлся...