3. Примеры реализации операций

1. Построить дерево из n узлов минимальной высоты, или идеально сбалансированное дерево (количество узлов левого и правого поддеревьев такого дерева должны отличаться не более чем на единицу).

Рекурсивный алгоритм построения:

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.