位置: 编程技术 - 正文

JS中的二叉树遍历详解(js实现二叉查找树)

编辑:rootadmin

推荐整理分享JS中的二叉树遍历详解(js实现二叉查找树),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:js二叉树遍历,js二叉树层次遍历,二叉树遍历java,js实现二叉树数据结构,js二叉树遍历,js二叉树遍历方法,js二叉树遍历方法,js二叉树遍历方法,内容如对您有帮助,希望把文章链接给更多的朋友!

二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树。这篇文章主要在JS中实现二叉树的遍历。

一个二叉树的例子

广度优先遍历广度优先遍历是从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。实现:<!--more-->使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候,执行循环:取出队列的一个节点,如果该结点的左子树为非空,则将该结点的左子树入队列;如果该结点的右子树为非空,则将该结点的右子树入队列。(描述有点不清楚,直接看代码吧。)

递归遍历觉得用这几个字母表示递归遍历的三种方法不错:D:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。先序遍历:DLR中序遍历:LDR后序遍历:LRD顺着字母表示的意思念下来就是遍历的顺序了 ^ ^

这3种遍历都属于递归遍历,或者说深度优先遍历(Depth-First Search,DFS),因为它总是优先往深处访问。

先序遍历的递归算法:

JS中的二叉树遍历详解(js实现二叉查找树)

中序遍历的递归算法:

后序遍历的递归算法:

非递归深度优先遍历其实对于这些概念谁是属于谁的我也搞不太清楚。有的书里将二叉树的遍历只讲了上面三种递归遍历。有的分广度优先遍历和深度优先遍历两种,把递归遍历都分入深度遍历当中;有的分递归遍历和非递归遍历两种,非递归遍历里包括广度优先遍历和下面这种遍历。个人觉得怎么分其实并不重要,掌握方法和用途就好 :)

刚刚在广度优先遍历中使用的是队列,相应的,在这种不递归的深度优先遍历中我们使用栈。在JS中还是使用一个数组来模拟它。这里只说先序的:额,我尝试了描述这个算法,然而并描述不清楚,按照代码走一边你就懂了。

看了这一篇,找到了非递归后序的算法,所以在这里把非递归的遍历方法补充完整。非递归中序先把数的左节点推入栈,然后取出,再推右节点。

非递归后序(使用一个栈)这里使用了一个临时变量记录上次入栈/出栈的节点。思路是先把根节点和左树推入栈,然后取出左树,再推入右树,取出,最后取跟节点。

非递归后序(使用两个栈)这个算法的思路和上面那个差不多,s1有点像一个临时变量。

Morris遍历这个方法即不用递归也不用栈实现三种深度遍历,空间复杂度为O(1)(这个概念我也不是特别清楚org)(这三种算法我先放着,有空再研究)Morris先序:

Morris中序:

Morris后序:

标签: js实现二叉查找树

本文链接地址:https://www.jiuchutong.com/biancheng/377434.html 转载请保留说明!

上一篇:简述JavaScript提交表单的方式 (Using JavaScript Submit Form)(简述javascript的作用)

下一篇:基于javascript显示当前时间以及倒计时功能(javascript definitive guide)

  • 小规模季度不超30万需要交什么税
  • 计提城市维护建设费和教育费附加的会计分录
  • 交社保不发工资怎么办
  • 物业费专用发票税率
  • 税法对固定资产大修理
  • 应收账款转让的标志
  • 怎么扣除未支付的钱
  • 组织职工捐款取得的现金计入什么会计科目?
  • 增值税附征优惠政策
  • 手撕发票怎么区分地区开具
  • 长期合同收入与应收帐款如何处理?
  • 应征消费税的汽车为啥不能抵扣
  • 哪些票据可以挂公司名下
  • 发票上传多久可以验旧
  • 税务行业软件
  • 收付实现制下预收款算收入吗
  • 年初未分配利润在借方表示什么
  • 建筑行业一般纳税人税率是多少
  • 小规模纳税人可以抵扣增值税专用发票吗
  • 库存现金进账单会计分录
  • 应付职工薪酬借方负数是什么意思
  • 解决的英文
  • 电子商业承兑与银行承兑哪个好
  • 机票的保险费能开发票吗
  • 公司给部分员工交公积金
  • 固定资产出售收入属于什么收入
  • linux网络管理实训总结
  • 其他货币资金包括哪些内容
  • 期末损益类科目结转
  • 税控盘抵减
  • php中实现文件上传的函数是什么
  • 消费税的会计分录怎么写
  • 一个简单的html文档一般且必须包含哪些标签
  • php文件乱码怎么办
  • 蜜蜂 (© Angela Parker/Offset)
  • 第三方库引用
  • pytorch_lightning.utilities.exceptions.MisconfigurationException: You requested GPUs: [1] But...
  • 企业的罚款支出指企业的行政罚款
  • IIS 7.5 asp Session超时时间设置方法
  • 特征提取原理
  • 微信小程序怎么制作自己的小程序
  • ps调整边缘在哪里快捷键
  • 帝国cms怎么安装不了
  • mysql主从同步的优点
  • python数组合并并排序
  • 饭馆增值税
  • 企业所得税征税范围是
  • 普通发票的进项票怎么做分录
  • 其他应付款在借方资产负债表怎么填
  • 应收账款计提坏账影响利润吗
  • 免征的增值税如何处理
  • 出口退税企业退税流程
  • 老板从公司借款怎么处理
  • 税控系统设备可以全额抵扣吗
  • 行政单位合并财务怎么办
  • 租赁行业的成本
  • 利润分配未分配利润怎么结转
  • 工业企业固定资产折旧年限
  • 设置行政机构的主要依据是
  • MySQL 5.6.14 win32安装方法(zip版)
  • 进程死锁原因
  • mac steam一直更新
  • winole.exe - winole是什么进程
  • win7怎么进行系统还原
  • cf游戏截图在哪个文件夹
  • 更加有效率
  • css教程笔记
  • cocos2d开发app
  • java script教程
  • linux实现shell
  • js实现二叉查找树
  • Python通过DOM和SAX方式解析XML的应用实例分享
  • Python高手之路第3版PDF下载
  • android获取设备输出声音
  • 税控发票开票软件金税盘版口令怎么解锁?
  • 如何在网上查看自己的营业执照
  • 武汉税务电话号码
  • 税务网上抄报流程是什么
  • 贵州税务发票流向查询
  • 拟录用是正式录用吗
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设