基于二叉树的层次遍历算法分析
2021-03-15 19:29
标签：实现 code span ini color 重复 nbsp 基于 基本原理 基本原理： 通过利用队列对每一层的节点从左至右依次进队，然后对已经进队的上一层进行出队，直到所有队列全部出队，该函数结束。 算法分析： 第一，先将根节点的左右孩子进队，然后再访问根节点。（如果没有左右孩子则不进队，直接结束函数） 第二，判断队列是否为空，如果不为空，则进入循环体。 第三，先将出队一个节点，然后再访问根节点，最后将该节点的左右孩子进队。（如果没有左或或右孩子则不进队，则不进行任何操作） 第四，重复第三步骤，直到队列为空。 代码介绍： // 二叉树的层次遍历（借助队列实现） 基于二叉树的层次遍历算法分析 标签：实现 code span ini color 重复 nbsp 基于 基本原理 原文地址：https://www.cnblogs.com/cheng111/p/cheng111-erchashudecengcibianli.html
// 参数：二叉树根指针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); //判断左孩子是否存在，如果存在，则进队
}
}
上一篇：java测试类