Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 39 из 67

Алгоритмыобходадерева

Существуют три алгоритма обхода деревьев, которые естественно следуют из самой структуры дерева.

1. 
   Обход слева направо: Left-Root-Right (сначала посещаем левое поддерево, затем – корень и, наконец, правое поддерево).
   
2. 
   Обход сверху вниз: Root-Left-Right(посещаем корень до поддеревьев).
   
3. 
   Обход снизу вверх: Left-Right-Root (посещаем корень после поддеревьев).
   

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

Пусть для операндов Аи Ввыполняется операция сложения.

Привычная форма записи в виде А+Вназывается инфиксной.Форма записи, в которой знак операции следует перед операндами +АВ, называется префиксной, если же операция записывается после операндов АВ+ – постфиксной.

Рассмотрим небольшой пример, пусть задано выражение А+В*С. Так как умножение имеет более высокий приоритет, то данное выражение можно переписать в виде А+(В*С). Для записи выражения в постфиксной форме сначала преобразуем ту часть выражения, которая вычисляется первой, в результате получим: А+(ВС*).

Теперь запишем в постфиксной форме операцию сложения между операндами А и (ВС*): АВС*+.

Таким образом, выражение А+В*Св постфиксном виде АВС*+,

префиксная форма записи будет иметь вид +*АВС.

Рассмотрим различные обходы дерева на примере формулы: ((a+b/c)*(d–e*f )). Дерево формируется по принципу:

• 
  в корне размещаем операцию, которая выполнится последней;
  
• 
  далее узлы-операции, операнды – листья дерева.
  

Обход1(Left-Root-Right) дает обычную инфиксную запись выражения

(без скобок):

a+ b/ c * d– e* f.





Обход2(Root-Left-Right) – префиксную запись выражения (без скобок):

* + a / b c – d* ef.





Обход3(Left-Right-Root) – постфиксную запись выражения:

abc / + de f * – * .