В дереве поиска можно найти место каждого элемента, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значений встречающихся данных.
Использование деревьев поиска значительно сокращает время решения задачи.
Правильно организованным деревом считается идеально сбалансированное дерево, то есть для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 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.
Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип построения идеально сбалансированного дерева.