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

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                     .
    // структура одного элемента стека
    struct Element
    {
          Tree* node;   //адрес узла дерева - информационное поле
          Element* next; // указатель на следующий элемент списка
    };

    struct Stack
    {
          Element* head;              // адрес вершины стека
    };

   Функции добавления и извлечения элемента из стека изменятся следую-
щим образом:
        // определение функции добавления в стек нового элемента
        void PushStack(Stack& s, Tree* ptr)
        {
             Element* p=new Element;
             p->next=s.head;
             p->node=ptr;
             s.head=p;
    }

    // определение функции извлечения элемента из стека
    int PopStack(Stack& s, Tree*& ptr)
    {
          if(s.head==NULL)
               return -1;
          ptr=s.head->node;
          Element* p=s.head;
          s.head=s.head->next;
          delete p;
          return 1;
    }

    Создается переменная temp, с помощью которой осуществляется про-
смотр вершин дерева.
    Адрес текущей вершины помещается в стек, затем осуществляется пере-
ход к левому поддереву (temp=temp->left), т.е. текущей вершиной стано-
вится левый потомок. И так продолжается до тех пор, пока не достигнем
крайнего левого узла и обработаем его (temp=NULL). Далее извлекаем узел
из стека, печатаем его значение и переходим к его правому потомку. Если
правого потомка у узла нет, из стека извлекается очередная вершина. Если же

                                            98