Алгоритм Postfix
Построение из постфиксной записи
Реализация
Алгоритм Prefix
- Если не достигнут конец строки ввода, прочитать очередной символ.
- Создать новую вершину дерева, записать в нее этот символ.
- Если символ - операция, то:
- вызвать алгоритм Prefix для левого поддерева;
- вызвать алгоритм Prefix для правого поддерева.
Вновь воспользуемся описанием типа данных ukaz, приведенным на рис. 12.1:
procedure prefix(var p: ukaz);begin new(p); read(p^.symbol); if p^.symbol in ['+','-','*','/'] then begin prefix(p^.left); prefix(p^.right); end else begin p^.left:= nil; p^.right:= nil; endend; begin ... prefix(root); ...end.Для простоты предположим, что правильное арифметическое выражение подается в одной строке, без пробелов, а каждый операнд записан одной буквой. Кроме того, снова будем считать, что из записи удалены все скобки.
- Если не достигнут конец строки ввода, прочитать очередной символ,если этот символ - операнд, то занести его в стек2),иначе (символ - операция):
- создать новый элемент, записать в него эту операцию;
- достать из стека два верхних (последних) элемента, присоединить их в качестве левого и правого операндов в новый элемент;
- занести полученный "треугольник" в стек.
По окончании работы этого алгоритма в стеке будет содержаться ровно один элемент - указатель на корень построенного дерева.