JavaScript（JS）前序遍历，中序遍历，后序遍历，层序遍历，图⽂详解两种
（递归与迭。。。
1、
前序遍历⾸先访问根结点然后遍历左⼦树，最后遍历右⼦树。
在遍历左、右⼦树时，仍然先访问根结点，然后遍历左⼦树，最后遍历右⼦树。
若⼆叉树为空则结束返回，否则：
（1）访问根结点。
（2）前序遍历左⼦树。
（3）前序遍历右⼦树 。
需要注意的是：遍历左右⼦树时仍然采⽤前序遍历⽅法。
如图
前序遍历结果：ABCDEFGHI
已知后序遍历和中序遍历，就能确定前序遍历。
/
/ ⾮递归实现，迭代实现
var preorderTraversal=function(root){
if(!root)return[]
let res =[]
let queue =[root]
while(queue.length){
let temp = queue.pop()
res.push(temp.val)
if(temp.right) queue.push(temp.right)//  因为栈先进后出所以将right放前if(temp.left) queue.push(temp.left)
}
return res
};
先序中序后序遍历二叉树// 递归实现
var preorderTraversal=function(root,res=[]){
if(!root)return[]
res.push(root.val)
preorderTraversal(root.left,res)
preorderTraversal(root.right,res)
return res
};
2、
中序遍历⾸先遍历左⼦树，然后访问根结点，最后遍历右⼦树。若⼆叉树为空则结束返回，否则：（1）中序遍历左⼦树
（2）访问根结点
（3）中序遍历右⼦树
如图所⽰⼆叉树，中序遍历结果：CBDAGFHEI
// ⾮递归实现
var inorderTraversal=function(root){
if(!root)return[]
let res =[]
let stack =[]
while(stack.length || root){
//  循环遍历左节点
while(root){
stack.push(root)
root = root.left
}
let temp = stack.pop()
res.push(temp.val)
root = temp.right
}
return res
};
//递归实现
var inorderTraversal=function(root,res =[]){
if(!root)return[]
if(root.left)inorderTraversal(root.left,res)
res.push(root.val)
if(root.right)inorderTraversal(root.right,res)
return res
};
3、
后序遍历⾸先遍历左⼦树，然后遍历右⼦树，最后访问根结点，在遍历左、右⼦树时，仍然先遍历左⼦树，然后遍历右⼦树，最后遍历根结点。即：
若⼆叉树为空则结束返回，
否则：
（1）后序遍历左⼦树
（2）后序遍历右⼦树
（3）访问根结点
如图所⽰⼆叉树
后序遍历结果：CDBGHFIEA
已知前序遍历和中序遍历，就能确定后序遍历。
// ⾮递归实现，前序遍历是根左右，后序为左右根，将前序实现为根右左，再将数组反转即得后序遍历，左右根var  postorderTraversal  = function (root ) {    if (!root ) return  []
let  res = []
let  stack = [root ]
while (stack .length ){
let  temp = stack .pop ()
if (temp .left ) stack .push (temp .left )  //  前序根左右调换为，根右左        if (temp .right ) stack .push (temp .right )        res .push (temp .val )
}
return  res .reverse ()  //  将结果反转即为后序};
4、

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。