Занятие 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.

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

Поиск и включение элемента в дерево.

Задача. Задана последовательность слов. Определить частоту вхождения каждого из слов в последовательности.

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

Program Poisk;

Uses

Crt;

Type

Words = ^WordTree;

WordTree = record

Data: string;

k: integer;

Left, Right: Words;

end;

Var

n: integer;

kd: Words;

x: string;

f: text;

Procedure Tree(x: string; Var p: Words);

Begin

if p=nil

then

begin

new(p);

with p^ do

begin

k:= 1;

Data:= x;

Left:= Nil;

Right:= Nil;

end;

end;

else

if x>p^.Data

then

Tree(x. p^.Left)

else

if x<p^.Data

then

Tree(x. p^.Right)

else

Inc(p^.k);

End;

Procedure PrintTree(t: Words; 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, ',(', k, ')');

PrintTree(Right, h+1);

end;

End;

Begin

ClrScr;

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

reset(f);

write('n=');

readln(n);

kd:= Nil;

while n>0 do

begin

readln(f,x);

Tree(x, kd);

Dec(n);

end;

close(f);

PrintTree(kd, 0);

readln;

End.

Эта задача называется задачей поиска по дереву с включением.

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

Не нашли, что искали? Воспользуйтесь поиском: