Question

二叉树的层次遍历

请高手解释一下二叉树的层次遍历的精髓，最好是能用数学思维的，不只是敲出代码。谢谢。

Answer 1

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
void HierarchyBiTree(BiTree Root){
LinkQueue *Q; // 保存当前节点的左右孩子的队列

InitQueue(Q); // 初始化队列

if (Root == NULL) return ; //树为空则返回
BiNode *p = Root; // 临时保存树根Root到指针p中
Visit(p->data); // 访问根节点
if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列

while (!QueueEmpty(Q)) // 若队列不空，则层序遍历 { DeQueue(Q, p); // 出队列
Visit(p->data);// 访问当前节点

if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列
if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列
}

DestroyQueue(Q); // 释放队列空间
return ;
这个已经很详细了！你一定可以看懂的！加油啊！

Answer 2

树: A
/ \
B F
/ \ \
C D G
/ \
E F
从上到下，从左到右：A、B、F、C、D、G、E、F

Answer 3

Answer 4

void level (BTNode *p)
{
int front,rear;
BTNode *que[maxSize];
front=rear=0;
BTNode *q;
if(p!=NULL){
rear=(rear+1)%maxSize;
que[rear]=p;
while(front !=rear){
front =(front+1)%maxSize;
q=que[front];
Visit(q);
if(q->lchild!=NULL){
rear=(rear+1)%maxSize;
que[rear]=q->lchild;
}
if(q->rchild!=NULL){
rear=(rear+1)%maxSize;
que[rear]=q->rchild;
}}}

Answer 5

按层来，从左往右数