Занятие 4. Идеально сбалансированное дерево.

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

Использование деревьев поиска значительно сокращает время решения задачи.

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

Сформируем идеально сбалансированное дерево, элементами которого являются N чисел, вводимых с клавиатуры.

Поскольку требуется построить идеально сбалансированное дерево, то его узлы в процессе построения должны распределяться равномерно. Сформируем правило равномерного распределения узлов при известном их числе:

• Взять один узел в качестве корня.

• Построить левое поддерево с числом узлов n1=N div 2 тем же способом.

• Построить правое поддерево с числом узлов n2=N-n1-1 тем же способом.

Program BalansTree;

Uses

Crt;

Type

Pt = ^Node;

Node = record

Data : integer;

Left, Right : Pt;

end;

Var

n : integer;

kd : Pt;

f : text;

Function Tree(n : integer) : Pt;

Var

NewNode : Pt;

x, n1, n2 : integer;

Begin

if n=0

then

Tree := Nil

else

begin

n1 := n Div 2;

n2 := n–n1–1;

read(f,x);

new(NewNode);

with NewNode^ do

begin

Data := x;

Left := Tree(n1);

Right := Tree(n1);

end;

Tree := NewNode;

end;

End;

Procedure PrintTree(t : Pt; h : integer);

Var

i : integer;

Begin

if t<>nil

then

with t^ do

begin

PrintTree(Left, h+1);

for i := 1 to h do

write(' ');

writeln(Data:6);

PrintTree(Right, h+1);

end;

End;

Begin

ClrScr;

assign(f, 'c:\f.pas');

reset(f);

write('n=');

readln(n);

kd := Tree(n);

PrintTree(kd, 0);

readln;

End.

Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип построения идеально сбалансированного дерева.