二叉树的层次遍历也称广度优先遍历,是一种按照逐层遍历的二叉树遍历方式。
广度优先遍历需要借助辅助队列来存取各个节点。
实现方法如下:
//层次遍历
void LevelOrder(BiTree T)
{
LinkQueue Q;//辅助队列
InitQueue(Q);//初始化
BiTree p;
EnQueue(Q, T);
while (!IsEmpty(Q))
{
DeQueue(Q, p);
putchar(p->data);
if (p->lchild != NULL)
{
EnQueue(Q, p->lchild);
}
if (p->rchild != NULL)
{
EnQueue(Q, p->rchild);
}
}
}
首先根节点入队,当队列不空时,出队队首元素并打印相应节点的内容。
如果出队的节点有左孩子或者右孩子,则入队左孩子节点或者右孩子节点,如此循环。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)