层次遍历二叉树.docx
需积分: 0 129 浏览量
2023-03-16
12:47:05
上传
评论
收藏 19KB DOCX 举报
概念
二叉树的层次遍历是指从二叉树的根结点开始，从上往下逐层遍历，同一层中的
结点按从左往右的顺序访问。层次遍历需要借助一个辅助队列，利用队列先进先
出的特性，存放访问过的结点，以便下一层继续按照结点的左右次序访问它们的
孩子。
算法
层次遍历的基本步骤如下：
（1）从根结点开始，访问根结点，并进行入队操作。
（2）若队不为空，就进行出队操作，访问出队结点的左右孩子，并入队。继续
循环，直至队列为空。
层次遍历二叉树的算法如下：
void ccorder(BiTree t){
BiTree p;
SqQueue qlist,*q;
q=&qlist;
q->rear=0;
q->front=0;
p=t;
if(p!=NULL){
printf("%c",p->data);
q->data[q->rear]=p;
q->rear=(q->rear+1)%MAX;
while(q->front!=q->rear){
p=q->data[q->front];
q->front=(q->front+1)%MAX;
if(p->lchild!=NULL){
printf("%c",p->lchild->data);
q->data[q->rear]=p->lchild;
q->rear=(q->rear+1)%MAX;
}
if(p->rchild!=NULL){
printf("%c",p->rchild->data);
q->data[q->rear]=p->rchild;
q->rear=(q->rear+1)%MAX;
}
}
}
}
资源评论
