 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Примеры реализации операций
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.
ЛЕКЦИЯ № 10. Графы
Поиск по сайту: