47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

5440. Фізична культура як суспільне явище 131.5 KB
  Фізична культура як суспільне явище Метою лекції єознайомлення студентів з основними завданнями дисципліни Вступ до спеціальності фізичне виховання,визначення місця фізичної культури в загальній культурі суспільства та оволодіння основ...
5441. Предмет, метод, система трудового права 56.5 KB
  Предмет, метод, система трудового права Предмет регулювання трудового права України. Метод правового регулювання трудових відносин. Функції трудового права України. Система трудового права України. Предмет регулювання трудового пр...
5442. Джерела трудового права україни 47 KB
  Джерела трудового права україни План 1. Поняття джерел трудового права України, їх класифікація. 2. Конституція України як основне джерело трудового права. 3. Кодекс законів про працю України та інші законодавчі акти України, що регулюють трудові ві...
5443. Основні історичні етапи розвитку науки 81.5 KB
  Основні історичні етапи розвитку науки План Передумови виникнення науки. Основні етапи розвитку науки. Особливості класичної науки. Революція в природознавстві в кінці ХІХ ст. - початку ХХ ст. і формування...
5444. Теоретичні основи процесу навчання у вищій школі 81 KB
  Теоретичні основи процесу навчання у вищій школі План Педагогічний процес у вищому навчальному закладі та особливості його організації. Закономірності та принципи навчання у ВНЗ. Методи і засоби навчання у вищій школі. Основні поня...
5445. Спадкові хвороби людини 47 KB
  Спадкові хвороби людини 1. Класифікація складових хвороб людини. 2. Хромосомні хвороби,спричинені порушенням кількості або структури хромосом 3. Моногенні (молекулярні) спадкові захворювання 1. Спадкові захворювання з\'являються внаслідок ...
5446. Оценка технико-экономических показателей ремонтно-механического цеха 231.5 KB
  Введение Рыночная экономика в современных условиях предъявляет высокие требования к организации производства и труда на промышленных предприятиях. При этом основным путем к повышению производительности труда на предприятиях отечественного машиностро...
5447. Модное слово 21 века 46.5 KB
  Модное слово 21 века То, что в языке, как и в любой среде, существует своя мода - давно не новость. Она меняется с течением времени. Немалое значение оказывает на нее, развитие новых технологий, изменения в политике, бизнесе, производстве, кул...
5448. Сравнение двух вариантов заготовки детали Вас шестерня 3.73 MB
  Введение В рамках дипломного проекта будет рассматриваться деталь Вал-шестерня. Для детали будет проведён анализ технологичности, который позволит оценить её технологичность, т.е. возможность рациональной обработки с помощью стандартных инструмент...