Примеры реализации операций
1. Построить дерево из з узлов минимальной высоты, или идеально сбалансированное дерево (количество узлов левого и правого поддеревьев такого дерева должны отличаться не более чем на единицу).
Рекурсивный алгоритм построения:
1) первый узел берется в качестве корня дерева;
2) тем же способом строится левое поддерево из nl узлов;
3) тем же способом строится правое поддерево из nr узлов;
nr = n – nl – 1
В качестве информационного поля будем брать номера узлов, вводимые с клавиатуры. Рекурсивная функция, реализующая данное построение, будет выглядеть следующим образом:
Function Tree(n: Byte): TreeLink;
Var t: TreeLink; nl,nr,x: Byte;
Begin
If n = 0 then Tree:= nil
Else
Begin
nl:= n div 2;
nr = n – nl – 1;
writeln('Введите номер вершины );
readln(x);
new(t);
t^.inf:= x;
t^.left:= Tree(nl);
t^.right:= Tree(nr);
Tree:= t;
End;
{Tree}
End.
2. В бинарном упорядоченном дереве найти узел с заданным значением ключевого поля. Если такого элемента в дереве нет, то добавить его в дерево.
Procedure Search(x: Byte; var t: TreeLink);
Begin
If t = nil then
Begin
New(t);
t^inf:= x;
t^.left:= nil;
t^.right:= nil;
End
Else if x < t^.inf then
Search(x, t^.left)
Else if x > t^.inf then
Search(x, t^.right)
Else
Begin
{обработка найденного элемента}
…
End;
End.
