三行代码递归实现二叉树层序遍历

三行代码递归实现二叉树层序遍历简述二叉树的层序遍历网上大部分都是使用队列的出队和入队来实现的,这次我用三行代码递归实现二叉树的层序遍历.层序下图是一个简单的二叉树,层序就是一行一行的往下读取,这个二叉树的层序结果便是:1234567(图画的比较丑,强迫症看着难受,看官忍一下)递归分析要想使用递归,必须有两个条件:函数参数类型相同递归必须有出口在二叉树中找到上面的两个条件,与

大家好,又见面了,我是你们的朋友全栈君。

简述

二叉树的层序遍历网上大部分都是使用队列的出队和入队来实现的,这次我用三行代码递归实现二叉树的层序遍历.

层序

下图是一个简单的二叉树,层序就是一行一行的往下读取,这个二叉树的层序结果便是:
1234567

这里写图片描述
(图画的比较丑,强迫症看着难受,看官忍一下)

递归分析

要想使用递归,必须有两个条件:

  1. 函数参数类型相同
  2. 递归必须有出口

在二叉树中找到上面的两个条件,与前中后三种遍历一样,函数参数为节点的,递归出口是当左右孩子为空的时候.传入根节点,然后依次递归访问左右孩子,直至为空.

重点

那么问题来了,递归遍历的数据保存到那?如何做到保存后是层序的顺序?

继续观察这张图
这里写图片描述

第一层
根节点标记为1元素是层序输出的第一个值
第二层
标记为2的元素是层序输出的第二个值,同时他是标记为1节点的左孩子
标记为3的元素是层序输出的第三个元素,同时他是标记为1的节点的右孩子.
第三层
标记为4的元素是输出的第四个元素,他是标记为2节点的左孩子
标记为5的元素是输出的第五个元素,他是标记为2节点的右孩子

很容易找到一个规律:

  • 每一个节点左孩子在层序中输出的位置是该节点在层序输出位置的二倍
  • 每一个节点右孩子在层序中输出的位置是该节点在层序输出位置的二倍加一
  • 根节点在层序输出的位置为1

    也就是:
    假设当前节点输出的位置是i,那么他的左孩子层序输出的位置是2*i,他的右孩子在层序输出的位置为2*i+1

代码实现

根据上面得出的结论,就可以写出层序遍历的递归代码了,知道了节点层序输出的位置,那么遍历时候直接保存到指定位置,等所有节点遍历结束后再统一输出,这个与前中后遍历是不一样的.
既然是根据位置去保存,那么当然是使用数组了,位置就是数组的下标,根据下标进行存放,操作非常方便.

这一段代码,是把字符二叉树层序遍历

int tree2str(bitree *b,char *a,int i)
{
    if(b->left!=NULL)
    {
        tree2str(b->left,a,2*i);
    }
    if(b->right!=NULL)
    {
        tree2str(b->right,a,2*i+1);
    }
    *(a+i)=b->data;
}

注意
参数a为数组的首地址,调用时候传递参数i初始值为1,代表第一层,既就是根界点,当递归函数执行完毕时候,所有的元素都在对应的位置,a[0]元素始终为空,因为是从1开始存放的,所以调用之后输出的时候应该从a+1的位置开始,字符串结束应该是’\0’,输出前补上防错.
这里写图片描述
(本人测试环境:系统Ubuntu16.04LTS 编译器GCC5.4,字符串末尾没有添加’\0’未出错,在vc6.0会出现烫烫烫烫烫烫烫烫烫……)

结束

回到最初,标题说是三行代码,实际上为了看的方便在if函数后面加了花括号,我觉得一行代码的标志应该是一个分号,既一个语句;所以上面的也算是三行代码了.

如果上面的不算三行代码,那就看下面

int tree2str(bitree *b,char *a,int i)
{
    if(b->left!=NULL)       tree2str(b->left,a,2*i);
    if(b->right!=NULL)      tree2str(b->right,a,2*i+1);
    *(a+i)=b->data;
}

好了现在很直观的三行了[完].

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/143300.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 列车调度问题[通俗易懂]

    列车调度问题[通俗易懂]题目:高铁货运站的调配问题我们国家大力发展道路交通基础设施,最近这些年修建了大量的高铁线路,以促进国内的物资运输和调配,ZZ是一个超级货运站,是连接亚欧货运的枢纽站,现在ZZ货运站列车调度铁轨的结构如下图所示。两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意…

  • CListCtrl自绘「建议收藏」

    CListCtrl自绘「建议收藏」CListCtrl自绘有3种方法:第一种:使用WM_ERASEBKGND消息+NM_CUSTOMDRAW消息配合自绘WM_ERASEBKGND消息中绘制背景色,比如偶数行为灰色,奇数行为白色。NM_CUSTOMDRAW消息中设置字体的背景色和字体颜色。好处:保留了控件大多数的原有属性。不需要自己去输出每一个项目的字体。可以非常方便的设置背景色,以及文字的颜色。缺点:不能设置选中

  • 回溯法之01背包问题

    回溯法之01背包问题一、问题n皇后问题的解空间树是一颗排列树,而01背包问题的解空间树应该是一颗子集树。再简述下该问题:有n件物品和一个容量为c的背包。第i件物品的价值是v[i],重量是w[i]。求解将哪些物品装入背包可使价值总和最大。所谓01背包,表示每一个物品看成一个整体,要么全部装入,要么都不装入。这里n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}。01背…

    2022年10月17日
  • 画中画广告..例

    画中画广告..例<!–画中画广告开始–><tableborder=0cellspacing=0cellpadding=0align=left><tr><td&gt

  • springmvc的执行流程详解[通俗易懂]

    1.什么是MVCMVC是ModelViewController的缩写,它是一个设计模式 2.springmvc执行流程详细介绍 第一步:发起请求到前端控制器(DispatcherServlet)第二步:前端控制器请求HandlerMapping查找Handler        可以根据xml配置、注解进行查找第三步:处理器映射器Handle

  • idea快捷键汇总mac_mac版本IDEA快捷键「建议收藏」

    idea快捷键汇总mac_mac版本IDEA快捷键「建议收藏」本文中的快捷键均为系统默认配置。一、mac系统键盘和符号对应关系1.Control(或Ctrl)⌃2.CapsLock⇪3.Command(或Cmd)⌘4.Option(或Alt)⌥5.Shift⇧二、mac系统自有快捷键1.command系列1).command+space切换输入法2).command+M最小化当前窗口3).command+Q关闭当前程序(…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号