Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 99 стр.

            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
стек пуст, то это означает, что дерево было просмотрено полностью. В про-
тивном случае в стеке остались непросмотренные вершины, поэтому снова
осуществляется попытка прохода по левой ветке, но уже для другой текущей
вершины.

   // определение нерекурсивной функции распечатки элементов
   // дерева в порядке неубывания
   void PrintTree(Tree* root)
   {
         if(root==NULL) return;
         // создание вспомогательного стека
         Stack s; s.head=NULL;
         // текущий узел – корень дерева
         Tree* temp=root;
         // обход будет закончен, если все узлы окажутся
         // просмотренными, т.е. temp будет указывать
         // на несуществующий узел, и стек станет пустым
         while(s.head!=NULL || temp!=NULL)
         {
              // перемещаемся по крайней левой ветке,
              // исходящей из узла temp
              while(temp!=NULL)
              {
                   // помещаем каждый узел ветки в стек
                   PushStack(s,temp);
                   temp=temp->left;
              }
              // «прошли» последний узел левой ветки,
              // осуществляем возврат, т.е. извлекаем из стека
              // предыдущую вершину и сохраняем ее в temp
              PopStack(s,temp);
              // печатаем значение информационного поля
              printf("%d ",temp->info);
              // переходим на правого потомка текущего узла temp
              temp=temp->right;
         }
   }

    Задача 3. Дана символьная строка, содержащая правильное арифметиче-
ское выражение. Операндами выражения являются числа с плавающей точ-
кой, допустимые операции – сложение, вычитание, умножение и деление.
Требуется построить дерево разбора этого выражения.
    Деревом разбора выражения называется бинарное дерево, построенное по
следующим правилам:

                                      99