二叉树的递归遍历与非递归算法实现(二)
sdata.tag=1; // 这时要进入根的右子树了，所以根的 tag=1 ，下次碰到根时就可以访问了
Pushs(S,&sdata); //(p,1) 进栈，根还得进一次栈
p=p->rchild; // 遍历右子树
}
else //tag=1，这是说明了右子树访问完了返回，所以这次要对根进行访问了
{
printf( "%c\t" ,p->data);
p=NULL;
}
}
}
复制代码
二叉树的层次遍历
复制代码
// 二叉树的层次遍历
void LevelTraverse(BiTree T)
{
BiNode *p;
LinkQueue *Q;
InitQueue(Q);
EnQueue(Q,T);
while (!QueueEmpty(Q))
{
p=DeQueue(Q);
printf( "%c\t" ,p->data);
if (p->lchild!=NULL)
EnQueue(Q,p->lchild);
if (p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
复制代码
下面是完整代码：
View Code
/*测试数据*/
/* 分别是构建二叉树的输入数据以及先序、中序、后序、层次遍历序列：
ABE##C#D##F#GH#I##J##
ABECDFGHIJ
EBCDAFHIGJ
EDCBIGJGFA
ABFECGDHJI
*/
