前端数据结构--二叉树先序、中序、后序递归、非递归遍历

二叉树遍历二叉树的遍历是指从根节点出发，按照某种顺序依次访问所有节点，而且只访问一次，二叉树的遍历方式很多，如果限制了从左到右的方式，那么主要有4种：

前序遍历：根左右
中序遍历：左根右
后续遍历：左右根
层序遍历：按层级、从上到下，在同一层从左到右遍历

以上一篇的二叉树为例子，先序遍历先访问根节点，在访问左节点，在访问右节点，如图：

文章插图

先(根)序遍历（根左右）：A、B、D、E、C、F、G
中(根)序遍历（左根右） : D、B、E、A、F、C、G
后(根)序遍历（左右根） : D、E、B、F、G、C、A
层序序遍历（上到下，左到右）：A、B、C、D、E、F、G

递归实现先序、中序、后序、层序遍历二叉树的创建用上一篇链表方法存储的二叉树，只不过增加了4个遍历的方法而已。一颗大的树都是若干颗小树（根节点、左节点、右节点）构成，根节点也有可能是其他节点的左子树（树的根节点除外），所以递归遍历就是不断的递归子树的过程。
1 /* 2* @Description:3* @Version: 1.0 4* @Autor: longbs 5*/ 6 class Node { 7constructor (data = 'https://tazarkount.com/read/#') { 8this.data = https://tazarkount.com/read/data 9this.lNode = null10this.rNode = null11}12 }13 14 class BiTree {15root = null16nodeList = []17constructor (nodeList) {18this.root = new Node()19this.nodeList = nodeList20}21createNode (node) {22const data = this.nodeList.shift()23if (data ==='#') return24node.data = https://tazarkount.com/read/data25// 下一个元素是不是空节点, 如果不是创建左节点26if (this.nodeList[0] !=='#') {27node.lNode = new Node(data)28}29this.createNode(node.lNode)30 31// 下一个元素是不是空节点, 如果不是创建右节点32if (this.nodeList[0] !== '#') {33node.rNode = new Node(data)34}35this.createNode(node.rNode)3637}38preorderTraverse (node) {39if (node === null) return40console.log(node.data)41this.preorderTraverse(node.lNode)42this.preorderTraverse(node.rNode)43}44inorderTraverse (node) {45if (node === null) return46this.inorderTraverse(node.lNode)47console.log(node.data)48this.inorderTraverse(node.rNode)49}50postorderTraverse (node) {51if (node === null) return52this.postorderTraverse(node.lNode)53this.postorderTraverse(node.rNode)54console.log(node.data)55}56sequenceTraverse (root) {57if (!root) return58let queue = []59queue.push(root)60while (queue.length) {61const node = queue.shift()62console.log(node.data)63if(node.lNode) {64queue.push(node.lNode)65}66if (node.rNode) {67queue.push(node.rNode)68}69}70}71 }72 73 let arr = ['A','B','D','#','#','E','#','#','C','F','#', '#', 'G', '#', '#']74 let bi = new BiTree(arr)75 bi.createNode(bi.root)76 console.log(bi.root)77 78 console.log('----先序----')79 console.log(bi.preorderTraverse(bi.root))80 81 console.log('----中序----')82 console.log(bi.inorderTraverse(bi.root))83 84 console.log('----后序----')85 console.log(bi.postorderTraverse(bi.root))86 87 console.log('----层序----')88 console.log(bi.sequenceTraverse(bi.root))层级遍历使用了队列来实现，思路也比较简单，一开始入队根节点，出队最后一个节点，出队时把相关左节点、右节点入队，如此循环，队列为空即遍历完成。
非递归实现先序、中序、后序二叉树的递归遍历非常容易理解，但因为是递归调用需要在内存栈中分配内存用来保存参数，层数多了内存容易溢出。
非递归先序基本思路：使用数组来模拟栈的数据结构，首先根节点入栈，然后出栈，在出栈的时候把相关需要的节点按要求把左右节点入栈，如此循环一直到这个栈为空。
步骤：

根节点放入栈
取出栈顶的节点，把该节点结果放入数组
如果该右节点存在，将该节点右节点放入栈
如果该左节点存在，将该节点左节点放入栈
重复 2-4
栈为空退出循环

1 /* 2非递归：用栈来模拟递归 3*/ 4preorderNonRecursion (root) { 5if (!root) return '' 6let stack = [] 7let result = [] 8stack.push(root) 9while (stack.length) {10const node = stack.pop()11result.push(node.data)12 13// 如果存在右节点，先压入右节点14if (node.rNode) {15stack.push(node.rNode)16}17if (node.lNode) {18stack.push(node.lNode)19}20}21return result22}中序、后序代码基本思路类似代码如下：
1 // 非递归-中序 2inorderNonRecursion (root) { 3if (!root) return '' 4let stack = [] 5let result = [] 6// stack.push(root) 7while (root !== null || stack.length) { 8// 找到左节点 9while (root !== null) {10stack.push(root)11root = root.lNode12}13root = stack.pop()14result.push(root.data)15// 右节点16root = root.rNode17}18return result19}20// 非递归-后序21postorderNonRecursion (root) {22if (!root) return ''23let stack = []24let result = []25stack.push(root)26while (stack.length) {27const node = stack.pop()28result.unshift(node.data)29 30if (node.lNode) {31stack.push(node.lNode)32}33if (node.rNode) {34stack.push(node.rNode)35}36}37return result38}递归遍历、非递归遍历完整代码【前端数据结构--二叉树先序、中序、后序递归、非递归遍历】/* * @Description:* @Version: 1.0 * @Autor: longbs */class Node {constructor (data = 'https://tazarkount.com/read/#') {this.data = https://tazarkount.com/read/datathis.lNode = nullthis.rNode = null}}class BiTree {root = nullnodeList = []constructor (nodeList) {this.root = new Node()this.nodeList = nodeList}// 创建二叉树createNode (node) {const data = this.nodeList.shift()if (data ==='#') returnnode.data = https://tazarkount.com/read/data// 下一个元素是不是空节点, 如果不是创建左节点if (this.nodeList[0] !=='#') {node.lNode = new Node(data)}this.createNode(node.lNode)// 下一个元素是不是空节点, 如果不是创建右节点if (this.nodeList[0] !== '#') {node.rNode = new Node(data)}this.createNode(node.rNode)}// 先序preorderTraverse (node) {if (node === null) returnconsole.log(node.data)this.preorderTraverse(node.lNode)this.preorderTraverse(node.rNode)}// 中序inorderTraverse (node) {if (node === null) returnthis.inorderTraverse(node.lNode)console.log(node.data)this.inorderTraverse(node.rNode)}// 后序postorderTraverse (node) {if (node === null) returnthis.postorderTraverse(node.lNode)this.postorderTraverse(node.rNode)console.log(node.data)}// 层序sequenceTraverse (root) {if (!root) returnlet queue = []queue.push(root)while (queue.length) {const node = queue.shift()console.log(node.data)if(node.lNode) {queue.push(node.lNode)}if (node.rNode) {queue.push(node.rNode)}}}/*非递归-先序用栈来模拟递归*/preorderNonRecursion (root) {if (!root) return ''let stack = []let result = []stack.push(root)while (stack.length) {const node = stack.pop()result.push(node.data)// 如果存在右节点，先压入右节点if (node.rNode) {stack.push(node.rNode)}if (node.lNode) {stack.push(node.lNode)}}return result}// 非递归-中序inorderNonRecursion (root) {if (!root) return ''let stack = []let result = []// stack.push(root)while (root !== null || stack.length) {// 找到左节点while (root !== null) {stack.push(root)root = root.lNode}root = stack.pop()result.push(root.data)// 右节点root = root.rNode}return result}// 非递归-后序postorderNonRecursion (root) {if (!root) return ''let stack = []let result = []stack.push(root)while (stack.length) {const node = stack.pop()result.unshift(node.data)if (node.lNode) {stack.push(node.lNode)}if (node.rNode) {stack.push(node.rNode)}}return result}}let arr = ['A','B','D','#','#','E','#','#','C','F','#', '#', 'G', '#', '#']let bi = new BiTree(arr)bi.createNode(bi.root)console.log(bi.root)console.log('----递归先序----')console.log(bi.preorderTraverse(bi.root))console.log('----非递归先序----')console.log(bi.preorderNonRecursion(bi.root))console.log('----递归中序----')console.log(bi.inorderTraverse(bi.root))console.log('----非递归中序----')console.log(bi.inorderNonRecursion(bi.root))console.log('----递归后序----')console.log(bi.postorderTraverse(bi.root))console.log('----非递归后序----')console.log(bi.postorderNonRecursion(bi.root))console.log('----层序----')console.log(bi.sequenceTraverse(bi.root))

前端数据结构--二叉树先序、中序、后序 递归、非递归遍历

前端数据结构--二叉树先序、中序、后序递归、非递归遍历