Нерекурсивный обход дерева

struct node {
    int val;
    node *left,*right;
    node(int v, node *l,node *r):val(v),left(l),right(r) {}
};
void foo(node *t)
{
    std::stack<node*> s;
    s.push(NULL);
    node *tt = t;
    do {
        if (tt != NULL) {
            s.push(tt);
            std::cout << tt->val << '\n';
            tt = tt->left;
        } else {
            if (s.top() == NULL) break;
            tt = s.top();
            s.pop();
            tt = tt->right;
        }
    } while (true);
}

do
    {
        if (dr != NULL) 
            {
                 stack *elem=new stack;
                 elem->val=dr;
                 if (st==0)
                    {
                    st=elem;
                    st->next=0;
                    }
                     else
                   {
                      elem->next=st;//áûâøàÿ ãîëîâà ñòàíåò âòîðûì ýëåìåíòîì
                      st=elem;
                    }
                    cout << dr->val <<" ";
                    dr = dr->left;
            }  
            else 
            {               
                 if (st == NULL) break;//åñëè ñòåê ïóñò
                 dr = st;
                 stack *temp;
                 temp=st;
                 st=st->next;
                 delete temp;
                 dr = dr->right;
            }
    }while(true);

class MySteck{
    struct list_node*{
        list_node *next;
        int value;
        list_node(list_node *l, int v);
    };
    list_node *head;
    int sz; // количество узлов в списке
public:
    void push(int x);
    void pop();
    void top();
    bool empty();
    int size();
};

void print(node *t,int n)
{
    if (t != NULL) {
        print(t->right,n+1);
        for (int i = 0; i < n) std::cout << "  ";
        std::cout << t->val << '\n';
        print(t->left,n+1);
    }
}

void print_tree(uzel *root)//âûâåñòè äåðåâî
{
 if (root == 0) 
    return;
   print_tree(root->right);
   cout<<root->key<<" ";
   print_tree(root->left);
}

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
 
 
using namespace std;
 
 
 
//описание стэка
 
template<class telem> class stack
{
    telem *x;
    int top;
    int n;
public:
    stack(int size);
   ~stack(){delete x;}
   void push(telem y);
   telem pop();
   int emptry()
   {
       if (top==0) return 1;
       else return 0;
   }
};
 
template<class telem> stack<telem>::stack(int size)
{
    x = new telem [size];
    if(!x)
    {
    cout << "невозможно создать стек \n"; exit (1);
    }
    n = size;
    top =0;
}
 
template<class telem>void stack<telem>::push(telem y)
{
    if (top==n)
      {
          cout<<"стэк заполнен \n";return;
      }
    x[top]=y;
    top++;
}
 
template<class telem>telem stack<telem>::pop()
{
    if(top==0)
    {
    cout<< "Стек пуст\n";
    return 0;
    }
    top--;
    return x[top];
}
 
//postroenie dereva
 
template<class DataT> class tree
{
    DataT info;
    tree*llink;
    tree *rlink;
public:
    tree *root;
    tree(){root=NULL;};
    void in(tree<DataT> *&t);
    void btree1(tree<DataT> *t);
    void btree2(tree<DataT> *t);
    void btree3(tree<DataT> *t);
    void btree4(tree<DataT> *t);
    void btree5(tree<DataT> *t);
    void btree6(tree<DataT> *t);
 
};
 
template<class DataT>void tree<DataT>::in(tree<DataT> *&t)
{
    DataT c;
    cin>>c;
    if(c!='.')
    {
        t=new tree<DataT>;
        t->info=c;
        in(t->llink);
        in(t->rlink);
    }else{
        t=NULL;
    }
 
}
 
 
//рекурсивная реализация обхода в обратном порядке
template<class DataT>void tree<DataT>::btree1(tree<DataT> *t)
{
    if(t!=NULL)
    {
    btree1(t->llink);
    cout<<t->info;
    btree1(t->rlink);
    }
}
 
//рекурсивная реализация обхода в прямом порядке
template<class DataT>void tree<DataT>::btree2(tree<DataT> *t)
{
    if(t!=NULL)
    {
        cout<<t->info;
    btree2(t->llink);
        btree2(t->rlink);
    }
}
 
//рекурсивная реалзация обхода в концевом порядке
template<class DataT>void tree<DataT>::btree3(tree<DataT> *t)
{
    if(t!=NULL)
    {
        btree3(t->llink);
        btree3(t->rlink);
    cout<<t->info; 
   }
}
 
//Нерекурсивный обход в обратном порядке
template<class DataT>void tree<DataT>::btree4(tree<DataT> *t)
{
    stack <tree<DataT>*> x(100);
    tree<DataT> *p;
    p=t;
m: while(p!=NULL)
    {
    x.push(p);
    p=p->llink;
    }
    if(!x.emptry())
    {
    p=x.pop();
    cout<<p->info;
    p=p->rlink;
    goto m;
    }
}
 
//нерекурсивный обход в прямом порядке
template<class DataT>void tree<DataT>::btree5(tree<DataT> *t)
{
    stack <tree<DataT>*> s(100);
    tree<DataT> *p;
    p=t;
    s.push(p);
    while(!s.emptry())
    {
    p=s.pop();
    cout<<p->info;
    if(p->rlink!=NULL)
        s.push(p->rlink);
    if(p->llink!=NULL)
        s.push(p->llink);
    }
}
 
//нерекурсивный прямой обход
template<class DataT>void tree<DataT>::btree6(tree<DataT> *t)
{
    struct obxod{char info; obxod *link; void btree6(tree<DataT> *t);};
    stack <tree<DataT>*> s(100);
    tree *p;
    
    p=t;
    obxod *first=NULL;
    obxod *q;
    s.push(p);
    while(!s.emptry())
    {
    p=s.pop();
    q=new obxod;
    q->info=p->info;
    q->link = first;
    first = q;
 
    if(p->llink!=NULL)
        s.push(p->llink);
    if(p->rlink!=NULL)
        s.push(p->rlink);
    }
//вывод
 
    q=first;
    while(q!=NULL)
    {
    cout<<q->info;
    q=q->link;
    }
}
 
int comand=0;
 
//Тело основной рабочей программы
int main()
{
    cout<<"Вводите дерево";
    cout<<endl;
    tree<char> t;
    cout<<endl;
    t.in(t.root);
 
cout<<"Рекурсивный обратный обход:\n";
t.btree1(t.root);
   cout<<endl;
cout<<"Рекурсивынй прямой обход:\n";
t.btree2(t.root);
   cout<<endl;
cout<<"Рекурсивный концевой обход:\n";
t.btree3(t.root);
   cout<<endl;
cout<<"Нерекурсивный обратный обход:\n";
t.btree4(t.root);
   cout<<endl;
cout<<"Нерекурсивный прямой обход:\n";
t.btree5(t.root);
   cout<<endl;
cout<<"Нерекурсивный концевой обход:\n";
t.btree6(t.root);
   cout<<endl;
       
}

struct stack
{
  uzel *val;
  struct stack *next;//äîáàâèë â íà÷àëî èçâëåê â íà÷àëî
};
 
void push(stack *s,uzel *el)
{
    stack *elem=new stack;
    elem->next=s;
    elem->val=el;
    s=elem; 
}
 
uzel* pop(stack *s)
{
    stack *temp=s;
    s=s->next;
    stack *simp=temp;
    delete temp;
    return simp->val;
}
 
void print_tree_2(uzel *root)
{
    
    uzel *dr=root;
    stack *ss;
    push(ss,dr);
    while (ss!=0)
    {
        dr=pop(ss);
        cout<<dr->key;
        if (dr->right!=0)
         push(ss,dr->right);
        if (dr->left!=0)
         push(ss,dr->left);
    }
}