#include <stdio.h>

#include <iostream>

#include "stack.cpp"

#include "queue.cpp"

typedef struct Node{

    int data;

    struct Node*lchild;

    struct Node*rchild;

}BiNode,*BiTree;

void visit(BiTree T)

{

    printf("%d",T->data);

    return ;

}

void preorder(BiTree T)

{

    if(T!=NULL)

    {

        visit(T);

        preorder(T->lchild);

        preorder(T->rchild);

    }

}

void inorder(BiTree T)

{

    if(T!=NULL)

    {

        inorder(T->lchild);

        visit(T);

        inorder(T->rchild);

    }

}

void postorder(BiTree T)

{

    if(T!=NULL)

    {

        postorder(T->lchild);

        postorder(T->rchild);

        visit(T);

    }

}

//非递归中序遍历：

void inorder2(BiTree T)

{

    sqstack s;

    initstack(s);BiTree p=T;

    while(p||!stackempty(s))

    {

        if(p)

        {

            push(s,(int)p);//有一定问题，因为push函数参数写的int，而p应该是一个树的结点指针

            p=p->lchild;

        }

        else

        {

           pop(s,(int)p);

           visit(T);

           p=p->rchild;    

        }

    }

}

//非递归的先序遍历

void preorder2(BiTree T)

{

    sqstack s;

    initstack(s);BiTree p=T;

    while(p||!stackempty(s))

    {

      if(p)

      {

          visit(p);

          push(s,(int)p);

          p=p->lchild;

      }

      else

      {

          pop(s,(int)p);

          p->rchild;

      }

    }

}

//非递归后续遍历

void posorder(BiTree T)

{

    sqstack s;

    initstack(s);

    BiTree p=T;

    BiTree r=NULL;

    while(p||!stackempty(s))

    {

        if(p)

        {

            push(s,(int)p);

            p->lchild;

        }

        else

        {

            Gettop(s,(int)p);

            if(p->lchild&&p->rchild!=r)

            p=p->rchild;

            else

            {

                pop(s,(int)p);

                visit((BiTree)p->data);

                r=p;

                p=NULL;

            }

        }

    }

}

//层次遍历

void leveorder(BiTree T)

{

    sqQueue*Q;

    initqueue(Q);

    BiTree p;

    enterqueue(Q,(int)T);

    while(!empty(Q))

    {

        Dletequeue(Q,(int)p);

        visit(p);

        if(p->lchild!=NULL)

        enterqueue(Q,(int)p->lchild);

        if(p->rchild!=NULL)

        enterqueue(Q,(int)p->rchild);

    }

}

//线索二叉树

typedef struct ThreadNode{

    int data;

    struct ThreadNode*lchild;

    struct ThreadNode*rchild;

    int ltag,rtag;

}ThreadNode,*ThreaTree;