Занятие 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.
Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип построения идеально сбалансированного дерева.
Дата добавления: 2015-05-16; просмотров: 1022;