Для такого представления используют следующий алгоритм: изображаем корень дерева; .

Работа добавлена: 2018-07-05






Между деревьями общего вида (узел дерева может иметь более двух сыновей) и бинарными деревьями существует взаимно однозначное соответствие, поэтому бинарные деревья часто используют для представления деревьев общего вида. Для такого представления используют следующий алгоритм:

  1. изображаем корень дерева;
  2. по вертикали изображаем старшего сына этого корня;
  3. по горизонтали вправо от этого узла представляем всех его братьев;
  4. пп. 1, 2, 3 повторяем для всех его узлов.

Теорема. Число бинарных деревьев с n вершинами можно выразить формулой: . Например, для n=3 имеем

Проиллюстрируем этот пример графически:

Представление бинарных деревьев в связной памяти.

Прошитые деревья.

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

Если мы воспользуемся прошитым бинарным деревом, то вид узла для него будет таким:

Один из возможных способов прошивки бинарного дерева заключается в том, что для каждого узла, не имеющего левого поддерева, запоминается ссылка на непосредственного предшественника, а для каждого узла, не имеющего правого поддерева ,запоминается ссылка на его непосредственного преемника. Предшественников и преемников для узла определяют исходя из списка, который получается при прохождении рассматриваемого бинарного дерева в симметричном порядке. Для того, чтобы отличать ссылку на левого или правого сына (такие ссылки называютструктурными связями) от ссылки на предшественника или преемника узла (такие ссылки называют “нитями”), используются индикаторные поля LP и RP.

Пример. Рассмотрим бинарное дерево:

Использование “прошивок” существенно убыстряет прохождение дерева, позволяет не использовать стек, но при этом усложняются алгоритмы включения / исключения узла, т.к. в прошитом дереве необходимо управлять не только структурными связями, но и “нитями”.

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

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

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

  1. взять один узел в качестве корня;
  2. построить левое поддерево с количеством узлов nl = [n / 2] тем же способом;
  3. построить правое поддерево с количеством узлов nr = n – nl – 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;

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

Применение бинарных деревьев в алгоритмах поиска.

В односвязном списке невозможно использовать бинарные методы, они могут использоваться только в последовательной памяти. Однако, если использовать бинарные деревья, то в такой связной структуре можно получить алгоритм поиска со сложностью O(log2 N). Такое дерево реализуется следующим образом: для любого узла дерева с ключом Ti все ключи в левом поддереве должны быть меньше Ti, а в правом – больше Ti. В дереве поиска можно найти место каждого ключа, двигаясь, начиная от корня и переходя на левое или правое поддерево, в зависимости от значения его ключа. Из n элементов можно организовать бинарное дерево (идеально сбалансированное) с высотой не более чем log2N, которое определяет количество операций сравнения при поиске.

Function Search (x: integer; t: ElPtr): ElPtr;

{поле Data заменим на поле Key}

var f: boolean;

begin

f:=false;

while (t<>nil) and not f do

if x=t^. key then f:=true

else if x>t^. key then t:=t^. R_Son else t:=t^. L_Son;

Search:=t;

end;

Если получим, что значение функции = nil, то ключа со значениемx в дереве не найдено.

Function Search (x: integer; t: ElPtr): ElPtr;

begin

S^.key:=x;

while t^.key<>x do

if x > t^.key then then t:=t^. R_Son else t:=t^. L_Son;

Search:=t;

end;

Операция включения в СД типа бинарное дерево.

Рассмотрим случай постоянно растущего, но никогда не убывающего дерева. Хорошим примером этого является построение частотного словаря. В этой задаче задана последовательность слов, и нужно установить число появления каждого слова. Это означает, что, начиная с пустого дерева, каждое слово, встречающееся в тексте, ищется в нем. Если это слово найдено, то счетчик появления данного слова увеличивается; если же слово не найдено, то в дерево включается новое слово со значением счетчика = 1.

Type ElPtr = ^Element

Element = record

Key: integer;

n: integer;

L_Son, R_Son: ElPtr;

end;

Procedure Put (x: integer; var t: ElPtr);

begin

if t=nil then begin

New(t);

with t^  do begin

key:=x;  n:=1;  L_Son:=nil;  R_Son:=nil;

end;

end

else if x> t^.key then Put(x, t^.R_Son)

else if x<t^.key then Put(x, t^.L_Son)

else t^.n:=t^.n+1;

end;

Хотя задача этого алгоритма –поиск с включением, но его можно использовать и для сортировки, т.к. он напоминает сортировку с включением. А так как вместо массива используется дерево, то пропадает необходимость перемещения элементов выше места включения. Для того, чтобы сортировка этого алгоритма была устойчивой, алгоритм должен выполняться одинаково как при t^.key=x, так и при t^.key>x.

Анализ алгоритма поиска. Если дерево вырождается в последовательность то сложность в таком случае O(N) (в худшем случае). В лучшем же случае, если дерево сбалансировано, то сложность будет O(log2 N). Таким образом, имеем:

O(N)£ ПФВС£ O(log2 N).

Если считать, что вероятность появления любой структуры дерева одинакова, и ключи появляются с одинаковой вероятностью, то .

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

Операция исключения из бинарного дерева.

При удалении узла дерево должно оставаться упорядоченным относительно ключа:

а) удаляется лист;

б) удаляется узел с одним потомком (потомок слева или справа);

в) удаляется узел с двумя потомками, но в левом потомке нет правого поддерева;

г) общий случай.

Рассмотрим случай б):

if g^.L_Son=nil then begin

g:=t;

t:=t^.R_Son;

dispose(g);

end;

if g^.R_Son=nil then begin

g:=t;

t:=t^.L_Son;

dispose(g);

end;

Случай а) является частным случаем этого алгоритма.

Случай в):  r указывает на элемент, не имеющий правого поддерева.

g:=t;

g^.key:=r^.key;

g:=r;

r:=r^.L_Son;

dispose(g);

Случай г):

Procedure Get (x: integer; var t: ElPtr);

var g: ElPtr;

begin

if t=nil then {обработка исключительной ситуации, когда элемента с заданным ключом в дереве нет}

else if x>t^.key then Get(x, t^.R_Son)

else if x<t^.key then Get(x, t^.L_Son)

else begin

g:=t;

if g^.L_Son=nil then t:=g^.R_Son

else if g^.R_Son=nil then t:=g^.R_Son

else D(g^.L_Son); {найти r)

dispose(g);

end;

end;

Представление бинарного дерева в прямоугольной памяти.

При представлении дерева в прямоугольной памяти одно из полей R_Son или L_Son удаляется, т.к. необходимость в нем отпадает. Потомок может размещаться рядом, т.е. в непосредственной близости. Чтобы узнать, есть ли потомок, вводится булево поле L или R. Пусть, например, отсутствует левый потомок. Введем следующие переменные:

index = 0..max;

type Element = record

R_Son: index;

Data: BaseType;

L: boolean;

end;

var Tree = array [index] of Element;

A

b

c

f

g

D

e

h

T

F

T

F

F

1

2

3

4

5

6

7

8

Применение бинарных деревьев.

  1. Любое алгебраическое выражение, которое содержит переменные, числа, знаки операций и скобки можно представить в виде бинарного дерева (исходя из бинарности этих операций). При этом знак операции помещается в корне, первый операнд – в левом поддереве, а второй операнд – в правом. Скобки при этом опускаются. В результате все числа и переменные окажутся в листьях, а знаки операций – во внутренних узлах.

рассмотрим пример: 3* (x – 2) + 4.

Если же осуществить просмотр дерева в обратном порядке (левое поддерево, правое поддерево, корень), то получим обратную польскую запись.

  1. Классическая программа из класса интеллектуальных:построение деревьев решений. В этом случае не листовые (внутренние) узлы содержат предикаты – вопросы, ответы на которые могут принимать значения “да” или “нет”. На уровне листьев находятся объекты (альтернативы, с помощью которых распознаются программы). Пользователь получает вопросы, начиная с корня, и, в зависимости от ответа, спускается либо на левое поддерево, либо на правое. Таким образом, он выходит на тот объект, который соответствует совокупности ответов на вопрос.
  2. Применение практических задач.

Алгоритмы прохождения деревьев в глубину и в ширину.

Алгоритм прохождения дерева в глубину:

<пустой стек S>;

<пройти корень и включить его в стек S>;

while <стек S не пуст> do

begin  {пусть P – узел, находящийся в вершине стека S}

if <не все сыновья узла Р пройдены>

then <пройти старшего сына и включить его в стек S>

else begin

<исключить из вершины стека узел Р>;

if <не все братья вершины Р пройдены>

then <пройти старшего брата и включить его в стек S>

end;

end;

При прохождении представленного дерева в ширину (по уровням), список его вершин, записанных в порядке их посещения, будет выглядеть следующим образом:

A,  B, C, D, E,    F, G, H, I, J,    K.

Алгоритм прохождения дерева в ширину:

<взять две очереди О1 и О2>;

<поместить корень в очередь О1>;

while <О1 или О2 не пуста> do

if <О1 не пуста> then {Р – узел, находящийся в голове очереди О1}

begin

<исключить узел из очереди О1 и пройти его>;

<поместить все узлы, относящиеся к братьям этого узла Р в очередь О2>;

end

else <O1=O2; O2=Æ> и повторяем цикл.




Возможно эти работы будут Вам интересны.

1. Понятия указателей и массивов тесно связаны. Рассмотрим следующий фрагмент программы:

2. - используют при строительстве домов с тяжелыми стенамибетонными каменными кирпичными ленточный фундаме

3. -контроль и в этом случае используют метод радиационной интроскопии радиоскопии основанный на преобразова.

4. Автомобільний транспорт і його значення в житті людей. Виготовлення автомобіля 30-х років Ford з дерева

5. Если множество данных состоящее например из миллиона элементов хранится в виде бинарного дерева то для п

6. Языческие представления древних славян

7. Приматізбектелген алгоритм

8. Если присмотреться к истолкованиям истории такого рода пишет знаменитый русский философ С.

9. Основу ассортимента такого альпинария должны составлять настоящие альпийские растения выра

10. Мостом, соединяющим теоретические представления с педагогической практикой, служат принципы обучения