Динамические структуры данных. Алексеев А.Ю - 51 стр.

вариантов терминологии 1 и 2. В варианте 2 названия обходам даны соот-
ветственно тому, что в КЛП-порядке корень посещается перед посещением
узлов левого поддерева (прямой порядок), а в ЛКП-порядке корень посещает-
ся после обхода узлов левого поддерева (обратный порядок). В ЛПК-порядке
корень посещается после обхода узлов левого и правого поддеревьев (кон-
цевой порядок). Такая терминология основана на важной роли левого подде-
рева в каноническом соответствии бинарного дерева и леса (см. 3.3).
   Терминология варианта 5 явно связана с обходом бинарного дерева, пред-
ставляющего арифметическое выражение с бинарными операциями. Пусть,
например, дано арифметическое выражение
                         (a+b)*c−d/(e+f*g).
   На рис. 3.8 представлено соответствующее ему бинарное дерево.

                                  –

                       *                         /

               +           c              d              +


           a       b                                 e             *


                                                               f           g

                    Рис. 3.8. Бинарное дерево, представляющее
               арифметическое выражение ( a + b) * c – d / ( e + f * g )

   Тогда три варианта обхода этого дерева порождают три известные формы
записи арифметического выражения:
   1) КЛП − префиксную запись
               − * + a b c / d + e * f g;
   2) ЛКП − инфиксную запись (без скобок, необходимых для задания после-
довательности выполнения операций)
               a + b * c − d / e + f * g;
   3) ЛПК − постфиксную запись
               a b + c * d e f g * + / − .
   В качестве упражнения полезно дать интерпретацию и остальным вариан-
там названий обходов.


           Нерекурсивные процедуры обхода бинарных деревьев

   Учитывая важность эффективной реализации обходов бинарных деревьев,
рассмотрим нерекурсивные процедуры обходов. Общий нерекурсивный алго-

                                          51