时间: 2019-12-02阅读: 106标签: 树
JS中的二叉树遍历详解,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)
10bet,(这三种算法我先放着,有空再研究)
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) {
以上就是本文的全部内容,希望对大家的学习有所帮助。
经常有同学问树结构的相关操作,也写了很多次,在这里总结一下JS树形结构一些操作的实现思路,并给出了简洁易懂的代码实现。本文内容结构大概如下:
您可能感兴趣的文章:
- js数组循环遍历数组内所有元素的方法
- js中的for如何实现foreach中的遍历
- JS循环遍历JSON数据的方法
- JS数组的遍历方式for循环与for...in
- JQuery $.each遍历JavaScript数组对象实例
- JS 使用for循环遍历子节点查找元素
- JQuery遍历json数组的3种方法
- JavaScript数据结构和算法之二叉树详解
- nodejs实现遍历文件夹并统计文件大小
http://www.bkjia.com/Javascript/1111370.htmlwww.bkjia.comtruehttp://www.bkjia.com/Javascript/1111370.htmlTechArticleJS中的二叉树遍历详解,js二叉树历详解 二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树。 这篇文章主要在...
一、遍历树结构1. 树结构介绍
JS中树结构一般是类似于这样的结构:
let tree = [ { id: '1', title: '节点1', children: [ { id: '1-1', title: '节点1-1' }, { id: '1-2', title: '节点1-2' } ] }, { id: '2', title: '节点2', children: [ { id: '2-1', title: '节点2-1' } ] }]
为了更通用,可以用存储了树根节点的列表表示一个树形结构,每个节点的children属性(如果有)是一颗子树,如果没有children属性或者children长度为0,则表示该节点为叶子节点。
- 树结构遍历方法介绍
树结构的常用场景之一就是遍历,而遍历又分为广度优先遍历、深度优先遍历。其中深度优先遍历是可递归的,而广度优先遍历是非递归的,通常用循环来实现。深度优先遍历又分为先序遍历、后序遍历,二叉树还有中序遍历,实现方法可以是递归,也可以是循环。
广度优先和深度优先的概念很简单,区别如下:
深度优先,访问完一颗子树再去访问后面的子树,而访问子树的时候,先访问根再访问根的子树,称为先序遍历;先访问子树再访问根,称为后序遍历。广度优先,即访问树结构的第n+1层前必须先访问完第n层3. 广度优先遍历的实现
广度优先的思路是,维护一个队列,队列的初始值为树结构根节点组成的列表,重复执行以下步骤直到队列为空:
取出队列中的第一个元素,进行访问相关操作,然后将其后代元素(如果有)全部追加到队列最后。
下面是代码实现,类似于数组的forEach遍历,我们将数组的访问操作交给调用者自定义,即一个回调函数:
// 广度优先function treeForeach (tree, func) { let node, list = [...tree] while (node = list.shift()) { func(node) node.children list.push(...node.children) }}
很简单吧,~,~用上述数据测试一下看看:
treeForeach(tree, node = { console.log(node.title) })
输出,可以看到第一层所有元素都在第二层元素前输出:
节点1 节点2 节点1-1 节点1-2 节点2-1
- 深度优先遍历的递归实现
先序遍历,三五行代码,太简单,不过多描述了:
function treeForeach (tree, func) { tree.forEach(data = { func(data) data.children treeForeach(data.children, func) // 遍历子树 })}
后序遍历,与先序遍历思想一致,代码也及其相似,只不过调换一下节点遍历和子树遍历的顺序:
function treeForeach (tree, func) { tree.forEach(data = { data.children treeForeach(data.children, func) // 遍历子树 func(data) })}
测试:
treeForeach(tree, node = { console.log(node.title) })
输出:
本文由10bet发布于Web前端,转载请注明出处:JS中的二叉树遍历详解,js二叉树历详解
关键词: