Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Формирование бинарного дерева.




Читайте также:
  1. III этап: Формирование либеральной и социалистической оппозиций в Германии. Проблема национального объединения в политической жизни 30-40 гг.
  2. III. Формирование тоталитарного режима
  3. А. выбор инвестиционной стратегии, анализ рынка, формирование портфеля, пересмотр портфеля и анализ эффективности;
  4. Аналитический учет к сч.84 должен обеспечить формирование информации
  5. Билет 10. 10.1. Формирование корпоративного имиджа организации.
  6. Билет №38. Формирование системы целей
  7. Бюджетный процесс, организация бюджетных процедур. Реформирование бюдж. процесса в РФ
  8. Валютный курс и факторы, влияющие на его формирование.
  9. Валютный курс и факторы, влияющие на его формирование. Основные методы регулирования валютных курсов.
  10. Виды валютных курсов и их формирование

 

При формировании бинарного дерева нужно задать некоторые ограничения. Рассмотрим пример, когда необходимо построить дерево из n вершин, имеющее минимальную высоту. Для достижения минимальной высоты необходимо, чтобы все уровни дерева, кроме, может быть, последнего, были заполнены. Для того чтобы сделать такое распределение, все поступающие нужно распределять поровну: слева и справа.

                               
 
n=1 n=2 n=3 n=4 n=5 n=6 n=7
 
             
   
 
 

 

 


Таким образом, правила для равномерного распределения при известном числе узлов n можно сформулировать с помощью следующего рекурсивного алгоритма:

1) взять один узел в качестве корня;

2) построить левое поддерево с количеством узлов n l = [n / 2] тем же способом;

3) построить правое поддерево с количеством узлов n r = n – n l – 1 тем же способом.

Описание узла дерева на языке Turbo Pascal выглядит таким образом:

Type ElPtr = ^Element

Element = record

Data: integer;

L_Son, R_Son: ElPtr;

end;

Идеально сбалансированное дерево обладает определенным свойством таким, что относительно каждого узла дерева количество узлов в левом и правом поддеревьях может отличаться максимум на 1.

Function Tree (n: integer): ElPtr;

var nl, nr, x: integer;

NewElement: ElPtr;

begin

if n=0 then Tree:=nil

else begin

nl:=n div 2;

nr:=n – nl – 1;

read (x); New (NewElement);

with NewElement do begin

Data:=x;

L_Son:=Tree (nl);

R_Son:=Tree )nr);

end;

Tree:=NewElement;

end;

end;

Эффективность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов.

 


Дата добавления: 2015-04-18; просмотров: 11; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты