JS中的二叉树遍历详解
二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树。
这篇文章主要在JS中实现二叉树的遍历。
一个二叉树的例子
var tree = { value: 1, left: { value: 2, left: { value: 4 } }, right: { value: 3, left: { value: 5, left: { value: 7 }, right: { value: 8 } }, right: { value: 6 } } }
广度优先遍历
广度优先遍历是从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。
实现:
<!--more-->
使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候,执行循环:取出队列的一个节点,如果该结点的左子树为非空,则将该结点的左子树入队列;如果该结点的右子树为非空,则将该结点的右子树入队列。
(描述有点不清楚,直接看代码吧。)
var levelOrderTraversal = function(node) { if(!node) { throw new Error('Empty Tree') } var que = [] que.push(node) while(que.length !== 0) { node = que.shift() console.log(node.value) if(node.left) que.push(node.left) if(node.right) que.push(node.right) } }
递归遍历
觉得用这几个字母表示递归遍历的三种方法不错:
D:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。
先序遍历:DLR
中序遍历:LDR
后序遍历:LRD
顺着字母表示的意思念下来就是遍历的顺序了 ^ ^
这3种遍历都属于递归遍历,或者说深度优先遍历(Depth-First Search,DFS),因为它总
是优先往深处访问。
先序遍历的递归算法:
var preOrder = function (node) { if (node) { console.log(node.value); preOrder(node.left); preOrder(node.right); } }
中序遍历的递归算法:
var inOrder = function (node) { if (node) { inOrder(node.left); console.log(node.value); inOrder(node.right); } }
后序遍历的递归算法:
var postOrder = function (node) { if (node) { postOrder(node.left); postOrder(node.right); console.log(node.value); } }
非递归深度优先遍历
其实对于这些概念谁是属于谁的我也搞不太清楚。有的书里将二叉树的遍历只讲了上面三种递归遍历。有的分广度优先遍历和深度优先遍历两种,把递归遍历都分入深度遍历当中;有的分递归遍历和非递归遍历两种,非递归遍历里包括广度优先遍历和下面这种遍历。个人觉得怎么分其实并不重要,掌握方法和用途就好 :)
刚刚在广度优先遍历中使用的是队列,相应的,在这种不递归的深度优先遍历中我们使用栈。在JS中还是使用一个数组来模拟它。
这里只说先序的:
额,我尝试了描述这个算法,然而并描述不清楚,按照代码走一边你就懂了。
var preOrderUnRecur = function(node) { if(!node) { throw new Error('Empty Tree') } var stack = [] stack.push(node) while(stack.length !== 0) { node = stack.pop() console.log(node.value) if(node.right) stack.push(node.right) if(node.left) stack.push(node.left) } }
看了这一篇,找到了非递归后序的算法,所以在这里把非递归的遍历方法补充完整。
非递归中序
先把数的左节点推入栈,然后取出,再推右节点。
var inOrderUnRecur = function(node) { if(!node) { throw new Error('Empty Tree') } var stack = [] while(stack.length !== 0 || node) { if(node) { stack.push(node) node = node.left } else { node = stack.pop() console.log(node.value) node = node.right } } }
非递归后序(使用一个栈)
这里使用了一个临时变量记录上次入栈/出栈的节点。思路是先把根节点和左树推入栈,然后取出左树,再推入右树,取出,最后取跟节点。
var posOrderUnRecur = function(node) { if(!node) { throw new Error('Empty Tree') } var stack = [] stack.push(node) var tmp = null while(stack.length !== 0) { tmp = stack[stack.length - 1] if(tmp.left && node !== tmp.left && node !== tmp.right) { stack.push(tmp.left) } else if(tmp.right && node !== tmp.right) { stack.push(tmp.right) } else { console.log(stack.pop().value) node = tmp } } }
非递归后序(使用两个栈)
这个算法的思路和上面那个差不多,s1有点像一个临时变量。
var posOrderUnRecur = function(node) { if(node) { var s1 = [] var s2 = [] s1.push(node) while(s1.length !== 0) { node = s1.pop() s2.push(node) if(node.left) { s1.push(node.left) } if(node.right) { s1.push(node.right) } } while(s2.length !== 0) { console.log(s2.pop().value); } } }
Morris遍历
这个方法即不用递归也不用栈实现三种深度遍历,空间复杂度为O(1)(这个概念我也不是特别清楚org)
(这三种算法我先放着,有空再研究)
Morris先序:
var morrisPre = function(head) { if(!head) { return } var cur1 = head, cur2 = null while(cur1) { cur2 = cur1.left if(cur2) { while(cur2.right && cur2.right != cur1) { cur2 = cur2.right } if(!cur2.right) { cur2.right = cur1 console.log(cur1.value) cur1 = cur1.left continue } else { cur2.right = null } } else { console.log(cur1.value) } cur1 = cur1.right } }
Morris中序:
var morrisIn = function(head) { if(!head) { return } var cur1 = head, cur2 = null while(cur1) { cur2 = cur1.left if(cur2) { while(cur2.right && cur2.right !== cur1) { cur2 = cur2.right } if(!cur2.right) { cur2.right = cur1 cur1 = cur1.left continue } else { cur2.right = null } } console.log(cur1.value) cur1 = cur1.right } }
Morris后序:
var morrisPost = function(head) { if(!head) { return } var cur1 = head, cur2 = null while(cur1) { cur2 = cur1.left if(cur2) { while(cur2.right && cur2.right !== cur1) { cur2 = cur2.right } if(!cur2.right) { cur2.right = cur1 cur1 = cur1.left continue } else { cur2.right = null printEdge(cur1.left) } } cur1 = cur1.right } printEdge(head) } var printEdge = function(head) {
以上就是本文的全部内容,希望对大家的学习有所帮助。
相关文章
- 本篇文章主要分享了通过window.navigator来判断浏览器及其版本信息的实例代码。具有一定的参考价值,下面跟着小编一起来看下吧...2017-01-23
- 这篇文章主要介绍了js如何实现浏览器打印功能,文中示例代码非常详细,帮助大家更好的理解和学习,感兴趣的朋友可以了解下...2020-07-15
- 这篇文章主要给大家介绍了关于Nest.js参数校验和自定义返回数据格式的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-28
- 下面小编就为大家带来一篇利用JS实现点击按钮后图片自动切换的简单方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-10-25
- 作为前端,一直以来都知道HTTP劫持与XSS跨站脚本、CSRF跨站请求伪造。防御这些劫持最好的方法是从后端入手,前端能做的太少。而且由于源码的暴露,攻击者很容易绕过防御手段。但这不代表我们去了解这块的相关知识是没意义的,本文的许多方法,用在其他方面也是大有作用。...2021-05-24
- 这篇文章主要为大家详细介绍了js+css实现回到顶部按钮back to top回到顶部按钮,感兴趣的小伙伴们可以参考一下...2016-03-03
- 那么今天我就用JavaScript代码来实现这个效果吧,那么首先介绍一下整个的思路,首先我们先将确定输入密码的位数,我的需求是5位,那么就用一个div标签包住5个input标签...2016-01-02
- 这篇文章主要为大家详细介绍了js实现上传图片及时预览的相关资料,具有一定的参考价值,感兴趣的朋友可以参考一下...2016-05-09
- 这篇文章主要介绍了js实现调用网络摄像头及常见错误处理,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-07
- 这篇文章主要为大家详细介绍了JS实现随机生成验证码,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-06
- 这篇文章主要介绍了js组件SlotMachine实现图片切换效果制作抽奖系统的相关资料,需要的朋友可以参考下...2016-04-19
- Vue.js通过简洁的API提供高效的数据绑定和灵活的组件系统.这篇文章主要介绍了vue.js 表格分页ajax 异步加载数据的相关资料,需要的朋友可以参考下...2016-10-20
- 为了网站的安全性,很多朋友都把密码设的比较复杂,但是如何密码不能明显示,不知道输的是对是错,为了安全起见可以把密码显示的,那么基于js代码如何实现的呢?下面通过本文给大家介绍JavaScript实现表单密码的隐藏和显示,需要的朋友参考下...2016-03-03
- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
- 这篇文章主要介绍了基于JavaScript实现文字超出部分隐藏 的相关资料,需要的朋友可以参考下...2016-03-01
- 这篇文章主要介绍了JS实现响应鼠标点击动画渐变弹出层效果代码,具有非常自然流畅的动画过度效果,涉及JavaScript针对鼠标事件的响应及页面元素样式的动态操作相关技巧,需要的朋友可以参考下...2016-03-28
- 这次文章要给大家介绍的是node.JS md5加密中文与php结果不一致怎么办,不知道具体解决办法的下面跟小编一起来看看。 因项目需要,需要Node.js与PHP做接口调用,发现nod...2017-07-06
- 系统的学习了一下angularjs,发现angularjs的有些思想根php的模块smarty很像,例如数据绑定,filter。如果对smarty比较熟悉的话,学习angularjs会比较容易一点,这篇文章给大家介绍angularjs filter用法详解,感兴趣的朋友一起学习吧...2015-12-29
- 这篇文章主要给大家介绍了一个关于JS正则匹配的踩坑记录,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-13
- 本文给大家介绍的是nodejs实现使用阿里大鱼短信API发送消息的方法和代码,有需要的小伙伴可以参考下。...2016-01-20