您的位置:澳门新葡8455最新网站 > 服务器运维 > JS中的二叉树遍历详明_javascript才干_脚本之家

JS中的二叉树遍历详明_javascript才干_脚本之家

发布时间:2019-12-09 15:19编辑:服务器运维浏览(162)

    二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树。这篇文章主要在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 } }}
    

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

    var levelOrderTraversal = function { throw new Error } var que = [] que.push while { node = que.shift() console.log if que.push if que.push }}
    

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

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

    var preOrder = function  { console.log; preOrder; preOrder; }}
    
    var inOrder = function  { inOrder; console.log; inOrder; }}
    
    var postOrder = function  { postOrder; postOrder; console.log; }}
    

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

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

    var preOrderUnRecur = function { throw new Error } var stack = [] stack.push while { node = stack.pop() console.log if stack.push if stack.push }}
    

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

    var inOrderUnRecur = function { throw new Error } var stack = [] while(stack.length !== 0 || node) { if { stack.push node = node.left } else { node = stack.pop() console.log node = node.right } }}
    

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

    var posOrderUnRecur = function { throw new Error } var stack = [] stack.push var tmp = null while { tmp = stack[stack.length - 1] if(tmp.left && node !== tmp.left && node !== tmp.right) { stack.push } else if(tmp.right && node !== tmp.right) { stack.push } else { console.log node = tmp } }}
    

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

    var posOrderUnRecur = function { var s1 = [] var s2 = [] s1.push while { node = s1.pop if { s1.push } if { s1.push } } while { console.log; } }}
    

    Morris遍历这个方法即不用递归也不用栈实现三种深度遍历,空间复杂度为OMorris先序:

    var morrisPre = function { return } var cur1 = head, cur2 = null while { cur2 = cur1.left if { while(cur2.right && cur2.right != cur1) { cur2 = cur2.right } if { cur2.right = cur1 console.log cur1 = cur1.left continue } else { cur2.right = null } } else { console.log } cur1 = cur1.right }}
    
    var morrisIn = function { return } var cur1 = head, cur2 = null while { cur2 = cur1.left if { while(cur2.right && cur2.right !== cur1) { cur2 = cur2.right } if { cur2.right = cur1 cur1 = cur1.left continue } else { cur2.right = null } } console.log cur1 = cur1.right }}
    
    var morrisPost = function { return } var cur1 = head, cur2 = null while { cur2 = cur1.left if { while(cur2.right && cur2.right !== cur1) { cur2 = cur2.right } if { cur2.right = cur1 cur1 = cur1.left continue } else { cur2.right = null printEdge } } cur1 = cur1.right } printEdge}var printEdge = function { 
    

    以上就是本文的全部内容,希望对大家的学习有所帮助。

    本文由澳门新葡8455最新网站发布于服务器运维,转载请注明出处:JS中的二叉树遍历详明_javascript才干_脚本之家

    关键词: