WorldodTech

Регистрация


Технологии вокруг нас

Скорость Wi-Fi сегодня

Новая 3D технология ...

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

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.

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.

3. Написать процедуры обхода дерева в прямом, симметричном и обратном порядке соответственно.

3.1. Procedure Preorder(t : TreeLink);

Begin

If t <> nil then

Begin

Writeln(t^.inf);

Preorder(t^.left);

Preorder(t^.right);

End;

End;

3.2. Procedure Inorder(t : TreeLink);

Begin

If t <> nil then

Begin

Inorder(t^.left);

Writeln(t^.inf);

Inorder(t^.right);

End;

End.

3.3. Procedure Postorder(t : TreeLink);

Begin

If t <> nil then

Begin

Postorder(t^.left);

Postorder(t^.right);

Writeln(t^.inf);

End;

End.

4. В бинарном упорядоченном дереве удалить узел с заданным значением ключевого поля.

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

Procedure Delete1(x : Byte; var t : TreeLink);

Var p : TreeLink;

Procedure Delete2(var q : TreeLink);

Begin

If q^.right <> nil then Delete2(q^.right)

Else

Begin

p^.inf := q^.inf;

p := q;

q := q^.left;

End;

End;

Begin

If t = nil then

Writeln('искомого элемента нет')

Else if x < t^.inf then

Delete1(x, t^.left)

Else if x > t^.inf then

Delete1(x, t^.right)

Else

Begin

P := t;

If p^.left = nil then

t := p^.right

Else

If p^.right = nil then

t := p^.left

Else

Delete2(p^.left);

End;

End.