Uedo

07.10.2020 02:54

Информатика

Есть ответ 👍

переделать программу на Паскале Разработать программу, реализующую следующий набор операций с двоичными деревьями поиска:
1. поиск вершины с заданным значением ключа с выводом счетчика появлений данного ключа.
2. добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений.
3. построчный вывод дерева в наглядном виде с обратно-симметричного обхода.
Все действия оформляются как подпрограммы.
TYPE
pNode = ^dNode;
dNode = RECORD
Inf: INTEGER;
Left,Right: pNode
END;
pStack = ^Item;
Item = RECORD
Inf: pNode;
next: pStack;
END;
VAR
Count, N, Num: INTEGER;
pRoot : pNode;

PROCEDURE Privetstvie();
BEGIN
WRITELN('Выберите действие:');
WRITELN('1-Построить дерево');
WRITELN('2-Обход в прямом направлении');
WRITELN('3-Обход в симметричном направлении');
WRITELN('4-Обход в обратно-симметричном направлении');
WRITELN('5-Итеративный Обход в симметричном направлении');
WRITELN('0-Выхода');
END;

PROCEDURE ShowOnward(VAR pCur: pNode; L: INTEGER);
BEGIN
IF pCur <> NIL
THEN
BEGIN
WRITELN('':4*L, pCur^.Inf);
ShowOnward(pCur^.Left, l+1);
ShowOnward(pCur^.Right, l+1)
END
END;

PROCEDURE ShowSymmetric(VAR pCur: pNode; L: INTEGER);
BEGIN
IF pCur <> NIL
THEN
BEGIN
ShowSymmetric(pCur^.Left, l+1);
WRITELN('':4*L, pCur^.Inf);
ShowSymmetric(pCur^.Right, l+1)
END
END;

PROCEDURE ShowBackSymmetric(VAR pCur: pNode; L: INTEGER);
BEGIN
IF pCur <> NIL
THEN
BEGIN
ShowBackSymmetric(pCur^.Right, L+1);
WRITELN('':4*L, pCur^.Inf);
ShowBackSymmetric(pCur^.Left, L+1)
END
END;

PROCEDURE Push(var s : pStack; Value : pNode);
var p : pStack;
BEGIN
NEW(p);
p^.next := s;
p^.Inf := Value;
s := p;
END;

PROCEDURE Pop(var s : pStack; var Value : pNode);
VAR
p : pStack;
BEGIN
IF s = NIL
THEN
Value := NIL
ELSE
BEGIN
Value := s^.Inf;
p := s;
s := s^.next;
DISPOSE(p);
END;
END;

PROCEDURE IterativeSymmetric(pCur: pNode);
VAR
s : pStack;
BEGIN
s := NIL;
REPEAT
WHILE pCur<> NIL
DO
BEGIN
Push(s, pCur);
pCur := pCur^.Left;
END;
IF s <> NIL
THEN
BEGIN
Pop(s, pCur);
WRITELN(pCur^.Inf);
pCur := pCur^.Right;
END;
UNTIL (s = NIL) AND (pCur = NIL);
END;

PROCEDURE ClearTree(pCur: pNode);
BEGIN
IF pCur <> NIL
THEN
BEGIN
ClearTree(pCur^.Left);
ClearTree(pCur^.Right);
DISPOSE(pCur);
Count := Count - 1;
IF Count = 0
THEN
pCur := NIL
END
END;

PROCEDURE CreateNode(var p : pNode; Data : INTEGER);
BEGIN
NEW(p);
p^.Inf := Data;
p^.Left := NIL;
p^.Right := NIL
END;

FUNCTION AddNode(var Root : pNode; Data : INTEGER) : BOOLEAN;
BEGIN
Result := TRUE;
IF Root = NIL
THEN
CreateNode(Root, Data)
ELSE
IF Root^.Inf < Data
THEN Result := AddNode(Root^.Right, Data)
ELSE
IF Root^.Inf > Data
THEN
Result := AddNode(Root^.Left, Data)
ELSE
Result := FALSE
END;

PROCEDURE AddNodes(VAR pCur: pNode; Count: INTEGER);
VAR
i, n : Integer;
BEGIN
RANDOMIZE;
FOR i := 1 TO Count
DO
REPEAT
n := Random(99);
UNTIL AddNode(pCur, n)
END;

BEGIN
pRoot := NIL;
Count := 0;
N := 6;
WHILE N <> 0
DO
BEGIN
Privetstvie();
READLN(N);
CASE N OF
0: BEGIN WRITELN('Удачи!До новых встреч.'); BREAK END;
1: BEGIN WRITELN('Число вершин дерева = '); READLN(Num); ClearTree(pRoot);
AddNodes(pRoot, Num); WRITELN('Дерево Создано') END;
2: IF pRoot <> NIL
THEN
ShowOnward(pRoot, 0)
ELSE
WRITELN('Дерево пустое');
3: IF pRoot <> NIL
THEN
ShowSymmetric(pRoot,0)
ELSE
WRITELN('Дерево пустое');
4: IF pRoot <> NIL
THEN
ShowBackSymmetric(pRoot, 0)
ELSE
WRITELN('Дерево пустое');
5: IF pRoot <> NIL
THEN
IterativeSymmetric(pRoot)
ELSE
WRITELN('Дерево пустое');
ELSE BEGIN WRITELN('Введенные данные неверны,повторите ввод'); N := 6 END
END
END
END.