JS中的二叉树遍历详解
二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树。
这篇文章主要在JS中实现二叉树的遍历。
一个二叉树的例子
vartree={ value:1, left:{ value:2, left:{ value:4 } }, right:{ value:3, left:{ value:5, left:{ value:7 }, right:{ value:8 } }, right:{ value:6 } } }
广度优先遍历
广度优先遍历是从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。
实现:
<!--more-->
使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候,执行循环:取出队列的一个节点,如果该结点的左子树为非空,则将该结点的左子树入队列;如果该结点的右子树为非空,则将该结点的右子树入队列。
(描述有点不清楚,直接看代码吧。)
varlevelOrderTraversal=function(node){ if(!node){ thrownewError('EmptyTree') } varque=[] 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-FirstSearch,DFS),因为它总
是优先往深处访问。
先序遍历的递归算法:
varpreOrder=function(node){ if(node){ console.log(node.value); preOrder(node.left); preOrder(node.right); } }
中序遍历的递归算法:
varinOrder=function(node){ if(node){ inOrder(node.left); console.log(node.value); inOrder(node.right); } }
后序遍历的递归算法:
varpostOrder=function(node){ if(node){ postOrder(node.left); postOrder(node.right); console.log(node.value); } }
非递归深度优先遍历
其实对于这些概念谁是属于谁的我也搞不太清楚。有的书里将二叉树的遍历只讲了上面三种递归遍历。有的分广度优先遍历和深度优先遍历两种,把递归遍历都分入深度遍历当中;有的分递归遍历和非递归遍历两种,非递归遍历里包括广度优先遍历和下面这种遍历。个人觉得怎么分其实并不重要,掌握方法和用途就好:)
刚刚在广度优先遍历中使用的是队列,相应的,在这种不递归的深度优先遍历中我们使用栈。在JS中还是使用一个数组来模拟它。
这里只说先序的:
额,我尝试了描述这个算法,然而并描述不清楚,按照代码走一边你就懂了。
varpreOrderUnRecur=function(node){ if(!node){ thrownewError('EmptyTree') } varstack=[] 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) } }
看了这一篇,找到了非递归后序的算法,所以在这里把非递归的遍历方法补充完整。
非递归中序
先把数的左节点推入栈,然后取出,再推右节点。
varinOrderUnRecur=function(node){ if(!node){ thrownewError('EmptyTree') } varstack=[] while(stack.length!==0||node){ if(node){ stack.push(node) node=node.left }else{ node=stack.pop() console.log(node.value) node=node.right } } }
非递归后序(使用一个栈)
这里使用了一个临时变量记录上次入栈/出栈的节点。思路是先把根节点和左树推入栈,然后取出左树,再推入右树,取出,最后取跟节点。
varposOrderUnRecur=function(node){ if(!node){ thrownewError('EmptyTree') } varstack=[] stack.push(node) vartmp=null while(stack.length!==0){ tmp=stack[stack.length-1] if(tmp.left&&node!==tmp.left&&node!==tmp.right){ stack.push(tmp.left) }elseif(tmp.right&&node!==tmp.right){ stack.push(tmp.right) }else{ console.log(stack.pop().value) node=tmp } } }
非递归后序(使用两个栈)
这个算法的思路和上面那个差不多,s1有点像一个临时变量。
varposOrderUnRecur=function(node){ if(node){ vars1=[] vars2=[] 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先序:
varmorrisPre=function(head){ if(!head){ return } varcur1=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中序:
varmorrisIn=function(head){ if(!head){ return } varcur1=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后序:
varmorrisPost=function(head){ if(!head){ return } varcur1=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) } varprintEdge=function(head){
以上就是本文的全部内容,希望对大家的学习有所帮助。