首页
编程语言

分类

当前位置: 云海天教程网 > 技术新闻 > 编程语言 >正文

基于二叉树的层次遍历算法分析

更新时间:2020-11-21  作者:佚名   来源:网络转载


	基于二叉树的层次遍历算法分析
[编程语言教程]

基本原理:

  通过利用队列对每一层的节点从左至右依次进队,然后对已经进队的上一层进行出队,直到所有队列全部出队,该函数结束。

 

算法分析:

  第一,先将根节点的左右孩子进队,然后再访问根节点。(如果没有左右孩子则不进队,直接结束函数)

  第二,判断队列是否为空,如果不为空,则进入循环体。

  第三,先将出队一个节点,然后再访问根节点,最后将该节点的左右孩子进队。(如果没有左或或右孩子则不进队,则不进行任何操作)

  第四,重复第三步骤,直到队列为空。

 

代码介绍:

// 二叉树的层次遍历(借助队列实现)
// 参数:二叉树根指针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);  //判断左孩子是否存在,如果存在,则进队
    }
}

 

基于二叉树的层次遍历算法分析

原文地址:https://www.cnblogs.com/cheng111/p/cheng111-erchashudecengcibianli.html

上一篇: activiti--事件监听 [随笔记录] 下一篇: IntelliJ IDEA打开带SVN信息的项目不显示SVN信息——解决方法 [随笔记录]
小编推荐
快速导航更多>>
JavaScript 教程 HTML5 教程 CSS3 教程 jQuery 教程 Vue.js 教程 Node.js 教程 SQL 教程 C 教程 PHP 教程 Linux 教程 Docker 教程 Nginx 教程 Python 教程 Java 教程

云海天教程网 版权所有

陕ICP备14013131号-3