47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

7203. Points and commas infigures 33 KB
  Тема: Points and commas infigures. Вид заняття: самостійна робота. Мета: розвивати самостійність студентів, розвивати вміння і навички роботи з додатковою літературою, оволодівати методами добору матеріалу, вчитися виділяти головне. Літе...
7204. Numbers. Percent. Telephone and fqx number 80.5 KB
  Тема:Numbers. Percent. Telephone and fqx number. Вид заняття: лекція-семінар. Мета: спонукати студентів до висловлювання англ. мовою шляхом постановки проблемних питань, практикувати навички усного мовлення розвивати у студе...
7205. Marketing. Лекція-семінар 74.5 KB
  Тема:Marketing Вид заняття: лекція-семінар. Мета: спонукати студентів до висловлювання англ. мовою шляхом постановки проблемних питань, практикувати навички усного мовлення розвивати у студентів навички самостійної роботи. Обладна...
7206. Radio commercials 62.5 KB
  Тема: Radio commercials Вид заняття: самостійна робота. Мета: розвивати самостійність студентів, розвивати вміння і навички роботи з додатковою літературою, оволодівати методами добору матеріалу, вчитися виділяти головне. Література: Л-2...
7207. Financial institutions 65.5 KB
  Тема: Financial institutions Вид заняття: лекція-семінар. Мета: спонукати студентів до висловлювання англ. мовою шляхом постановки проблемних питань, практикувати навички усного мовлення розвивати у студентів навички самостійної р...
7208. The role of the government 36 KB
  Тема: The role of the government Вид заняття: самостійна робота. Мета: розвивати самостійність студентів, розвивати вміння і навички роботи з додатковою літературою, оволодівати методами добору матеріалу, вчитися виділяти головне. Літера...
7209. Sources of finance 54.5 KB
  Тема: Sources of finance Вид заняття: лекція-семінар. Мета: спонукати студентів до висловлювання англ. мовою шляхом постановки проблемних питань, практикувати навички усного мовлення розвивати у студентів навички самостійної робот...
7210. Insuranse services of banks 45.5 KB
  Тема: Insuranse services of banks Вид заняття: лекція-cемінар Мета: спонукати студентів до висловлювання англ. мовою шляхом постановки проблемних питань, практикувати навички усного мовлення розвивати у студентів навички самостійн...
7211. Telephone Etiquette 31.5 KB
  Тема: TelephoneEtiquette Вид заняття: самостійна робота. Мета: розвивати самостійність студентів, розвивати вміння і навички роботи з додатковою літературою, оволодівати методами добору матеріалу, вчитися виділяти головне. Літерату...