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

рева b по уровням: сначала - из корня дерева, затем (слева направо) - из узлов,
сыновних по отношению к корню, затем (также слева направо) - из узлов, сы-
новних по отношению к этим узлам, и т.д.
    5. Для заданного леса с произвольным типом элементов:
    а) получить каноническое представление леса бинарным деревом;
    б) вывести изображение леса и бинарного дерева;
    в) перечислить элементы леса в горизонтальном порядке (в ширину).
    6. (Обратная задача.) Для заданного бинарного дерева с произвольным ти-
пом элементов:
    а) получить лес, канонически представленный этим бинарным деревом;
    б) вывести изображение бинарного дерева и леса;
    в) см.п.5,в.
    7. Рассматриваются бинарные деревья с элементами типа char.
    Заданы перечисления узлов некоторого дерева b в порядке КЛП и ЛКП.
Требуется:
    а) восстановить дерево b и вывести его изображение;
    б) перечислить узлы дерева b в порядке ЛПК.
    8. Рассматриваются бинарные деревья с элементами типа char. Заданы пе-
речисления узлов некоторого дерева b в порядке ЛКП и ЛПК. Требуется:
    а) восстановить дерево b и вывести его изображение;
    б) перечислить узлы дерева b в порядке КЛП.
    9. Формулу вида
         < формула > ::= < терминал > | ( < формула > < знак > < формула > )
         < знак > ::= + | - | *
         < терминал > ::= 0 | 1 | ... | 9 | a | b | ... | z
можно представить в виде бинарного дерева ("дерева-формулы") с эле-
ментами типа char согласно следующим правилам:
    - формула из одного терминала представляется деревом из одной вершины
с этим терминалом;
    - формула вида (f1 s f2) представляется деревом, в котором корень − это
знак s, а левое и правое поддеревья − соответствующие представления формул
f1 и f2. Например, формула ( 5 * ( a + 3 ) ) представляется деревом-формулой,
показанной на рис.3.12.
                                   *

                    5                             +

                                       a                  3

                              Рис. 3.12. Дерево-формулa

   Требуется:
   а) для заданной формулы f построить соответствующее дерево-формулу t;
   б) для заданного дерева-формулы t напечатать соответствующую
формулу f;
                                       64