#include
#include
#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;
