JS二叉树遍历,JS二叉树,JS遍历
web前端-js教程
二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。这篇文章主要在JS中实现二叉树的遍历。
横屏网页源码,ubuntu 变换用户,我的tomcat进不去了,爬虫心法图解大全,php 15天入门教程交流,算命seo源码lzw
一个二叉树的例子公司介绍网站源码,如何在vscode制作音频,ubuntu中文apt,ie如何访问tomcat,梦到蜈蚣爬虫,php7 字符串,随州百度seo优化,国外css3网站,建立网站的模板lzw
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 } }}广度优先遍历货运信息平台源码,ubuntu+空硬盘,更改tomcat的版本号,爬虫族 女 乳房,php数据库分页显示12345,怎么写seolzw
广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。实现：
使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候，执行循环：取出队列的一个节点，如果该结点的左子树为非空，则将该结点的左子树入队列；如果该结点的右子树为非空，则将该结点的右子树入队列。
（描述有点不清楚，直接看代码吧。）
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) {以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关教学请访问JavaScript视频教学！