- A+
所属分类：Web前端
二叉树遍历
二叉树的遍历是指从根节点出发，按照某种顺序依次访问所有节点，而且只访问一次，二叉树的遍历方式很多，如果限制了从左到右的方式，那么主要有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 { 7 constructor (data = '#') { 8 this.data = data 9 this.lNode = null 10 this.rNode = null 11 } 12 } 13 14 class BiTree { 15 root = null 16 nodeList = [] 17 constructor (nodeList) { 18 this.root = new Node() 19 this.nodeList = nodeList 20 } 21 createNode (node) { 22 const data = this.nodeList.shift() 23 if (data === '#') return 24 node.data = data 25 // 下一个元素是不是空节点, 如果不是创建左节点 26 if (this.nodeList[0] !== '#') { 27 node.lNode = new Node(data) 28 } 29 this.createNode(node.lNode) 30 31 // 下一个元素是不是空节点, 如果不是创建右节点 32 if (this.nodeList[0] !== '#') { 33 node.rNode = new Node(data) 34 } 35 this.createNode(node.rNode) 36 37 } 38 preorderTraverse (node) { 39 if (node === null) return 40 console.log(node.data) 41 this.preorderTraverse(node.lNode) 42 this.preorderTraverse(node.rNode) 43 } 44 inorderTraverse (node) { 45 if (node === null) return 46 this.inorderTraverse(node.lNode) 47 console.log(node.data) 48 this.inorderTraverse(node.rNode) 49 } 50 postorderTraverse (node) { 51 if (node === null) return 52 this.postorderTraverse(node.lNode) 53 this.postorderTraverse(node.rNode) 54 console.log(node.data) 55 } 56 sequenceTraverse (root) { 57 if (!root) return 58 let queue = [] 59 queue.push(root) 60 while (queue.length) { 61 const node = queue.shift() 62 console.log(node.data) 63 if(node.lNode) { 64 queue.push(node.lNode) 65 } 66 if (node.rNode) { 67 queue.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 */ 4 preorderNonRecursion (root) { 5 if (!root) return '' 6 let stack = [] 7 let result = [] 8 stack.push(root) 9 while (stack.length) { 10 const node = stack.pop() 11 result.push(node.data) 12 13 // 如果存在右节点，先压入右节点 14 if (node.rNode) { 15 stack.push(node.rNode) 16 } 17 if (node.lNode) { 18 stack.push(node.lNode) 19 } 20 } 21 return result 22 }
中序、后序代码基本思路类似代码如下：
1 // 非递归-中序 2 inorderNonRecursion (root) { 3 if (!root) return '' 4 let stack = [] 5 let result = [] 6 // stack.push(root) 7 while (root !== null || stack.length) { 8 // 找到左节点 9 while (root !== null) { 10 stack.push(root) 11 root = root.lNode 12 } 13 root = stack.pop() 14 result.push(root.data) 15 // 右节点 16 root = root.rNode 17 } 18 return result 19 } 20 // 非递归-后序 21 postorderNonRecursion (root) { 22 if (!root) return '' 23 let stack = [] 24 let result = [] 25 stack.push(root) 26 while (stack.length) { 27 const node = stack.pop() 28 result.unshift(node.data) 29 30 if (node.lNode) { 31 stack.push(node.lNode) 32 } 33 if (node.rNode) { 34 stack.push(node.rNode) 35 } 36 } 37 return result 38 }
递归遍历、非递归遍历完整代码
/* * @Description: * @Version: 1.0 * @Autor: longbs */ class Node { constructor (data = '#') { this.data = data this.lNode = null this.rNode = null } } class BiTree { root = null nodeList = [] constructor (nodeList) { this.root = new Node() this.nodeList = nodeList } // 创建二叉树 createNode (node) { const data = this.nodeList.shift() if (data === '#') return node.data = 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) return console.log(node.data) this.preorderTraverse(node.lNode) this.preorderTraverse(node.rNode) } // 中序 inorderTraverse (node) { if (node === null) return this.inorderTraverse(node.lNode) console.log(node.data) this.inorderTraverse(node.rNode) } // 后序 postorderTraverse (node) { if (node === null) return this.postorderTraverse(node.lNode) this.postorderTraverse(node.rNode) console.log(node.data) } // 层序 sequenceTraverse (root) { if (!root) return let 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))
