void PreOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{// 先序递归遍历T,对每个节点调用函数visit一次且仅一次
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild,Visit);
PreOrderTraverse(T->rchild,Visit);
}
}
void InOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//中序递归遍历T,对每个节点调用函数visit一次
if(T)
{
InOrderTraverse(T->lchild,Visit);
Visit(T->data);
InOrderTraverse(T->rchild,Visit);
}
}
typedef BiTree_1 SElemType;
#include "Stack.h"
#include "Stack.c"
Status InOrderTraverse1(BiTree *T,Status(*Visit)(TElemType))
{//中序遍历二叉树T的非递归算法(利用栈),对每个数据元素调用函数visit
SqStack S;
BiTree *p;
InitStack(&S);
while(T||!StackEmpty(S))
{
if(T)
{
Push(&S,T);
T=T->lchild;
}
else
{
Pop(&S,&T);
if(!Visit(T->data))
return ERROR;
T = T->rchild;
}
}
printf("\n");
return OK;
}
Status InOrderTraverse2(BiTree *T,Status(*Visit)(TElemType))
{//中序遍历二叉树T的非递归算法(利用栈),对每个数据元素调用函数visit,
SqStack S;
BiTree *p;
InitStack(&S);
Push(&S,T);
while(!StackEmpty(S))
{
while(GetTop(S,&p) && p)
{
Push(&S,p->lchild);
}
Pop(&S,&p);
if(!StackEmpty(S))
{
Pop(&S,&p);
if(!Visit(p->data))
return ERROR;
Push(&S,p->rchild);
}
}
printf("\n");
return OK;
}
void PostOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//后序递归遍历T,对每个节点调用函数Visit一次
if(T)
{
PostOrderTraverse(T->lchild,Visit);
PostOrderTraverse(T->rchild,Visit);
Visit(T->data);
}
}
void LevelOrderTraverse(BiTree *T,Status (*Visit)(TElemType))
{//层序递归遍历T,利用队列,对每个节点调用函数Visit一次
LinkQueue *q;
QElemType a;
q = (LinkQueue *)malloc(sizeof(struct QNode));
if(T)
{
InitQueue(&q);
EnQueue(q,T);
while(!QueueEmpty(q))
{
DeQueue(q,&a);
Visit(a->data);
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
printf("\n");
}
free(q);
}
Status PreOrderN(BiTree *T,Status (*Visit)(TElemType))
{//先序遍历二叉树T非递归算法
SqStack s;
BiTree *p;
InitStack(&s);
Push(&s,T);//根指针入栈
while(!StackEmpty(s))
{
while(GetTop(s,&p) && p)
{
if(!Visit(p->data))
return ERROR;
Push(&s,p->lchild);//向左走到尽头
}
Pop(&s,&p);//空指针出栈
if(!StackEmpty(s))
{
Pop(&s,&p);
Push(&s,p->rchild);
}
}
}
void PreOrder(BiTree *T,Status(*Visit)(TElemType))
{//先序遍历的递归算法
if(T)
{
Visit(T->data);
PreOrder(T->lchild,Visit);
PreOrder(T->rchild,Visit);
}
}
Status PostOrderN(BiTree *T,Status (*Visit)(TElemType))
{//后序遍历的非递归算法
SqStack s;
BiTree *p;
BiTree *r;
p = T;
InitStack(&s);
Push(&s,T);
while(!StackEmpty(s))
{
while(GetTop(s,&p) && p)
Push(&s,p->lchild);
Pop(&s,&p);
if(!StackEmpty(s))
{
GetTop(s,&p);
if(p->rchild && p->rchild!=r)
{
p=p->rchild;
Push(&s,p);
p=p->lchild;
}
else
{
Pop(&s,&p);
if(!Visit(p->data))
return ERROR;
r = p;
p=NULL;
Push(&s,p);
}
}
}
}
|