Логическое описание двоичного дерева

pTree=^Tree; Tree=record Корень:Inf; Лев,Прав:pTree end;

Корень
Лев	Прав

Арифметическое выражение как линейный список p погрузить в двоичное дерево

Голова(p) – функция с побочным эффектом

(Голова указывает на голову, p на хвост).

Функция Погрузить(р:pElem):pTree;

если атом?(р) то создается пень q,

иначе

q:=Конструирование(Погрузить (Голова(р)), Погрузить (Голова(р)), Погрузить (Голова(р)));

Погрузить =q

Реализация операций

Конструирование(р1:pTree; i:Inf; p2:pTree):pTree

Var p:pTree;

begin

NEW(p);

p^.Корень:=i;

p^.Лев:=p1;

p^.Прав:=p2;

Конструирование:=p

end

Теперь можно реализовать функцию Погрузить

ЛКП(р)

если р<>NIL то ЛКП(р^.Лев), TRT(p^.Корень), ЛКП(р^.Прав)

(TRT(i:Inf) - процедура обработки данного типа Inf, например печать)

Программа

ПАВ (строка символов) => LS => Линейный список

ПАВ (строка символов) => Задача! => Двоичное дерево

Линейный список => Погрузить => Двоичное дерево

Линейный список => Val => Значение выражения (число!)

Двоичное дерево => ЛПК => Обратная польская запись

Обратная польская запись => Стек => Значение выражения (число!)

program from_list_and_tree_to_list;

uses crt;

type

pList=^List;

List=record

next:pList;