基于二叉树的层次遍历算法分析
基本原理:
通过利用队列对每一层的节点从左至右依次进队,然后对已经进队的上一层进行出队,直到所有队列全部出队,该函数结束。
算法分析:
第一,先将根节点的左右孩子进队,然后再访问根节点。(如果没有左右孩子则不进队,直接结束函数)
第二,判断队列是否为空,如果不为空,则进入循环体。
第三,先将出队一个节点,然后再访问根节点,最后将该节点的左右孩子进队。(如果没有左或或右孩子则不进队,则不进行任何操作)
第四,重复第三步骤,直到队列为空。
代码介绍:
// 二叉树的层次遍历(借助队列实现)
// 参数:二叉树根指针T
// 输出:二叉树的层次遍历,中间没有空格,末尾不换行。
void HO(Tree T) { Queue S; //定义一个队列指针 Initiate(S); //创建一个空队列,进站元素类型为二叉树的结构体类型 if(!T) return; //判断二叉树是否为空,如果为空则直接退出 Tree p=T; //定义一个二叉树指针,并指向二叉树的根节点 printf("%c",p->data); //访问根节点 if(p->lchild) SQ_In(S, p->lchild); //判断右孩子是否存在,如果存在,则进队 if(p->rchild) SQ_In(S, p->rchild); //判断左孩子是否存在,如果存在,则进队 while(!SQ_IsEmpty(S)) //判断队列是否为空,如果不为空,则进入循环体 { SQ_Out(S, p); //出队一个元素 printf("%c",p->data); //访问根节点 if(p->lchild) SQ_In(S, p->lchild); //判断右孩子是否存在,如果存在,则进队 if(p->rchild) SQ_In(S, p->rchild); //判断左孩子是否存在,如果存在,则进队 } }