47263

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

Доклад

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

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

Русский

2014-03-31

20.87 KB

2 чел.

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

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

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

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

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

 

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

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

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

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


 

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

34483. Русская архитектура середины 18в. Школа Д. В.Ухтомского. Своеобразие архитектурного почерка 33 KB
  Ухтомского заключалась в руководстве правильной застройкой города. Ухтомского. Ухтомского выходили отличные зодчие примером чего может служить М. Ухтомского.
34484. Русская архитектура второй половины 18в. Деятельность М.Ф. Казакова 35 KB
  Казакова М. Казаков – ученик архитектурной школы известного русского зодчего Д. возглавил школу и команду Казаков приобрел большой строительный опыт: участвовал в создании Головинского дворца Триумфальных ворот на Страстной площади в честь коронации Екатерины II галереи Оружейной палаты. Впервые дарование Казакова как архитектора раскрылось во время его участия в восстановлении Твери после пожара в мае 1763 г.
34485. Русское искусство к.18в.: Эпоха русского классицизма. Портретный и исторический жанр в творчестве А.П. Лосенко. М.Шибанов – зачинатель крестьянского бытового жанра 34.5 KB
  Лосенко. Лосенко 1737 1773 сын крестьянина ставший потом директором Академии. Будучи воспитанником Академии художеств Лосенко создал большую историческую картину на евангельский сюжет Чудесный улов . Лосенко много внимания уделял он живописным этюдам обнаженного тела; в результате появились известные полотна Авель и Каин .
34486. Русское искусство к.18в.: Исторический пейзаж в творчестве Ф.М. Матвеева, С.Ф. Щедрина. Городской пейзаж в творчестве Ф.Я. Алексеева 31 KB
  Классицизм стремился подчинить себе все виды живописи превратить их по сути дела в исторический жанр. Среди его работ наиболее известны серии видов Павловского Гатчинского и Петергофского парков виды Каменного острова и декоративные панно для Михайловского дворца в Петербурге. Щедрин запечатлел конкретные виды архитектурных сооружений но главную роль отводил не им а окружающей природе с которой человек и его творения оказываются в гармоническом слиянии. Виды уютны уравновешенны в них есть прелесть открытия нового чувства природы...
34487. Русское искусство к.18в.: Портрет в творчестве Ф.С. Рокотова, Д.Г. Левицкого, В.Л. Боровиковского 34 KB
  : Портрет в творчестве Ф. Новый этап в развитии портретного искусства которое теперь не ограничивается запечатлением индивидуальных черт человека но проникает в его внутренний мир ознаменовался творчеством Ф. Удивительная одаренность Рокотова быстро принесла ему известность и признание при дворе но лучшие произведения относятся к московскому периоду его жизни где расцвел талант художника в области интимных камерных портретов. Созданный Рокотовым тип портрета камерный интимный портрет составляет целую эпоху в русской портретной...
34488. Архитектура первой половины 19в.: от классицизма к ампиру. А.Н. Воронихин. Ж.Т. де Томон, А.Д.Захаров, К.И. Росси 85 KB
  : от классицизма к ампиру. В Российской империи стиль ампир появился при Александре I. Для возведения Исакиевского собора Александр I пригласил начинающего французского архитектора Анри Луи Огюста Рикар де Монферрана впоследствии ставшего одним из основоположников русского ампира. Ампир от фр.
34489. Скульптура первой половины 19в.Скульпторы И.П. Мартос, Ф.Ф. Щедрин 26.5 KB
  Мартос Ф. Мартос создатель памятника Минину и Пожарскому а также Ф. Иван Петрович Мартос выдающийся русский скульптормонументалист. Портрет как самостоятельный жанр не занимает в творчестве Мартоса значительного места.
34490. Русское искусство н.19в.: Романтизм в творчестве живописца О.А. Кипренского 35.5 KB
  В изобразительном искусстве начала столетия сформировалось и новое направление вошедшее в историю под названием романтизма явление европейской культуры в XVIII XIX веках представляющее собой реакцию на Просвещение и стимулированный им научнотехнический прогресс. В начале XIX века романтизм стал обозначением нового направления противоположного классицизму и Просвещению. Героические походы Суворова на рубеже XVIII XIX столетий войны с Наполеоном и наконец народноосвободительная Отечественная война 1812 года а вслед за ней дворянское...
34491. Русское искусство н.19в.: Тенденции реализма в романтическом творчестве В.А.Тропинина. Пейзаж С.Ф. Щедрина 34.5 KB
  Тропинин. С этой же целью Тропинин пытался не показывать явную социальную принадлежность людей. “Портрет Арсения Тропинина†подкупает искренностью и чистотой эмоций написан он легко и обобщенно. “Кружевница†одно из самых популярных произведений Тропинина.