Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

ДЕРЕВО ВЫРАЖЕНИЯ

Часто информация, содержащаяся в узлах бинарного дерева, имеет отличающиеся атрибуты либо различное назначение. Такие деревья называются разнородными. Примером разнородного дерева является дерево, используемое для вычисления арифметических выражений.

Дерево выражения можно строить по инфиксной записи, но при этом алгоритм построения должен учитывать приоритеты выполнения операций и наличие скобок. Более простым путем является предварительное преобразование арифметического выражения из инфиксной записи в префиксную с использованием стека.

При построении дерева префиксная запись сканируется слева направо, и дерево строится также слева направо.

Рекурсивный алгоритм построения дерева выражения может быть описан следующим образом:

  • 1) получить очередной символ префиксной записи выражения и поместить его в узел дерева;
  • 2) если этот символ — операция,

то построить тем же способом его левое поддерево,

построить тем же способом его правое поддерево, иначе конец алгоритма.

Дерево выражения может строиться и по постфиксной записи, в этом случае запись выражения сканируется справа налево и дерево строится также справа налево.

Дерево выражения может быть реализовано как наследник бинарного дерева с символьным или строковым значением содержательного поля Value элемента дерева. Метод Build дерева выражения перекрывает одноименный метод бинарного дерева, так как реализуется иначе; все остальные методы бинарного дерева наследуются.

type

tOperatorSet = set of .. V; //тип - множество операторов tExprTree = class(tBinaryTree) //класс - дерево выражения

private

fOperators: tOperatorSet; //поле - множество операторов

public

// Возвращение True, если элемент выражения - оператор function lsOperator(ExprEI: tValue):Boolean;

procedure Build(var f: Text); //построение дерева выражения constructor Create; //создание пустого дерева

end; //tExprTree

Метод IsOperator проверяет, принадлежит ли очередной элемент выражения к множеству допустимых операторов fOperators. Метод Build дерева выражения перекрывает одноименный метод бинарного дерева, так как реализуется иначе. Конструктор Create помимо создания пустого дерева задает множество Operators разрешенных в данном выражении операторов. Остальные методы бинарного дерева наследуются.

В простейшем случае — для операндов и операторов, представляемых одним символом, — процедура построения дерева выражения по его префиксной записи, хранящейся в текстовом файле, имеет вид:

procedure TExprTree.Build(var f: Text);

// Построение дерева выражения по его префиксной записи в файле f

function BuildTree: pltem; //рекурсивная функция построения

var

Item: pltem; //элемент дерева выражения

Symbol: tValue; //символ выражения

begin

if not SeekEof(f)

then begin

Read(f, Symbol);

if SeekEoln(f) then ReadLn(f);

ltem:= New(pltem);

ltemA.Value:= Symbol;

if IsOperator(Symbol)

then begin // символ - оператор

ltemA.Left:= BuildTree; ltemA.Right:= BuildTree;

end

else begin // символ - операнд

ltemA.Left:= nil; ltemA.Right:=nil;

end;

BuildTree:= Item;

end;

end; //function BuildTree

begin

fRoot:= BuildTree;

end; //procedure TExprTree.Build

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы