树、二叉树的遍历

本文主要是介绍树、二叉树的遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树的遍历

• 1、树的结构

let tree = {val: 1,children: [{val: 2,children: [{val: 4, children:[]},{val: 5, children: []}]},{val: 3,children: [{val: 6, children:[]},{val: 7, children:[]},]}]}

• 2、深度优先遍历（递归）

    const fun = (root) => {console.log(root.val)root.forEach(fun)}

• 3、广度优先遍历（数组模拟队列的使用，右进左出）

1、新建队列，根节点入队
2、把对头出队
3、把对头的children挨个入队
4、重复2、3步，直到队列为空为止
const fun = (root) => {let arr = [root]while(arr.length){const o = arr.shift()o.children.forEach(item => {console.log(o.val)arr.push(item)})}}

二叉树的遍历

• 1、二叉树的结构

let binaryTree = {val: 1,left: {val: 2,left: {val: 4, left: null, right: null},right: {val: 5, left: null, right: null}},right: {val: 3,left: {val: 6, left: null, right: null},right: {val: 7, left: null, right: null}}}

• 2、前序遍历（根左右1、2、4、5、3、6、7）

// 递归方式实现
let arr = []const fun = (node) => {if(node){arr.push(node.val)fun(node.left)fun(node.right)}}fun(binaryTree) console.log(arr)
//栈的方式实现
if(!root){return []}let arr = []let stack = [root]while(stack.length){let o = stack.pop()arr.push(o.val)o.right && arr.push(o.right)o.left && arr.push(o.left)}console.log(arr)

• 3、中序遍历（左根右4、2、5、1、6、3、7）
• 4、后序遍历

这篇关于树、二叉树的遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---