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

三行代码递归实现二叉树层序遍历简述二叉树的层序遍历网上大部分都是使用队列的出队和入队来实现的,这次我用三行代码递归实现二叉树的层序遍历.层序下图是一个简单的二叉树,层序就是一行一行的往下读取,这个二叉树的层序结果便是: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)


相关推荐

  • 时间协议ntp服务器,时间服务器NTP搭建及NTP协议简介

    NTP协议简介目前在计算机上同步时间采用的NTP协议,我们可以在局域网中搭建NTP服务器来同步时间。NTP(NetworkTimeProtocol)是用来是计算机时间同步化的一种协议,他可以使计算机对其服务器或时钟源(如石英钟、GPS)做同步化,可以提供高精准度的时间校正。NTP可以通过原子钟、天文台、卫星等渠道获得精准时间,然后再按照NTP服务器等级进行传播。NTP的网络结构是分层管理的类树…

  • 2022考研数学二考试大纲最新_数学二线性代数考研大纲

    2022考研数学二考试大纲最新_数学二线性代数考研大纲2022年数学二考试大纲考试形式和试卷结构一、试卷满分及考试时间二、答题方式三、试卷内容结构四、试卷题型结构高等数学一、函数、极限、连续二、一元函数微分学三、一元函数积分学四、多元函数微积分学五、常微分方程线性代数一、行列式二、矩阵三、向量四、线性方程组五、矩阵的特征值及特征向量六、二次型考试科目:高等数学、线性代数考试形式和试卷结构一、试卷满分及考试时间试卷满分为150分,考试时间为180分钟.二、答题方式答题方式为闭卷、笔试.三、试卷内容结构高等教学 约80%线性代数 约20%四、试

  • Modelsim 10.2c 百度网盘下载「建议收藏」

    Modelsim 10.2c 百度网盘下载「建议收藏」百度网盘链接:链接:https://pan.baidu.com/s/1CGNg1Dy_S37P-obHoCncFg提取码:2eml

  • 微信扫码登陆(1)—扫码登录流程讲解、获取授权登陆二维码

    微信扫码登陆(1)—扫码登录流程讲解、获取授权登陆二维码扫码登录流程讲解、获取授权登陆二维码具体流程可以看微信官网的扫码登录文档地址:https://open.weixin.qq.com/cgi-bin/showdocument?action=dir_list&t=resource/res_list&verify=1&id=open1419316505&token=&lang=zh_CN其实官方文档已…

  • goland激活码 mac【注册码】

    goland激活码 mac【注册码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 转录调控必知数据库ENCODE,介绍及使用方法[通俗易懂]

    转录调控必知数据库ENCODE,介绍及使用方法[通俗易懂]按照上图的展示,目前的ENCODE通过多种测序数据来反应基因组变化的过程,分别是通过 Hi-C来观察三维基因组 ATAC-seq/chip-seq研究基因的转录调控 甲基化芯片来研究甲基化的调控作用 RNA-seq来研究基因表达的变化 RIP-seq研究在转录后调控的信息 我们可以通过ENCODE数据库来检索自己想要的数据。类似很多转录调控数据库也是在ENCODE数据库获得目标原始数据后,进行分析后构建的自己数据库。文…

    2022年10月29日

发表回复

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

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