2021年5月10日星期一

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

二叉树遍历

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

  1. 前序遍历：根左右
  2. 中序遍历：左根右
  3. 后续遍历：左右根
  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 = null10  this.rNode = null11  }12 }13 14 class BiTree {15 root = null16 nodeList = []17  constructor (nodeList) {18  this.root = new Node()19  this.nodeList = nodeList20  }21  createNode (node) {22  const data = this.nodeList.shift()23  if (data === '#') return24  node.data = data25  // 下一个元素是不是空节点, 如果不是创建左节点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) return40  console.log(node.data)41  this.preorderTraverse(node.lNode)42  this.preorderTraverse(node.rNode)43  }44  inorderTraverse (node) {45  if (node === null) return46  this.inorderTraverse(node.lNode)47  console.log(node.data)48  this.inorderTraverse(node.rNode)49  }50  postorderTraverse (node) {51  if (node === null) return52  this.postorderTraverse(node.lNode)53  this.postorderTraverse(node.rNode)54   console.log(node.data)55  }56  sequenceTraverse (root) {57  if (!root) return58  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))

层级遍历使用了队列来实现，思路也比较简单，一开始入队根节点，出队最后一个节点，出队时把相关左节点、右节点入队，如此循环，队列为空即遍历完成。

非递归实现先序、中序、后序

二叉树的递归遍历非常容易理解，但因为是递归调用需要在内存栈中分配内存用来保存参数，层数多了内存容易溢出。

非递归先序基本思路：使用数组来模拟栈的数据结构，首先根节点入栈，然后出栈，在出栈的时候把相关需要的节点按要求把左右节点入栈，如此循环一直到这个栈为空。

步骤：

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



 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 result22 }

中序、后序代码基本思路类似代码如下：

 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.lNode12   }13  root = stack.pop()14   result.push(root.data)15  // 右节点16  root = root.rNode17  }18  return result19  }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 result38 }

递归遍历、非递归遍历完整代码

/* * @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))

 

 













原文转载：http://www.shaoqun.com/a/731809.html

跨境电商：https://www.ikjzd.com/

亿恩网：https://www.ikjzd.com/w/1461

王惟：https://www.ikjzd.com/w/1744


二叉树遍历二叉树的遍历是指从根节点出发，按照某种顺序依次访问所有节点，而且只访问一次，二叉树的遍历方式很多，如果限制了从左到右的方式，那么主要有4种：前序遍历：根左右中序遍历：左根右后续遍历：左右根层序遍历：按层级、从上到下，在同一层从左到右遍历以上一篇的二叉树为例子，先序遍历先访问根节点，在访问左节点，在访问右节点，如图：先(根)序遍历（根左右）：A、B、D、E、C、F、G中(根)序遍历（左根右
麦言：https://www.ikjzd.com/w/1456
wish：https://www.ikjzd.com/w/105
沃尔玛：https://www.ikjzd.com/w/220
遇到亚马逊listing被封冻结的处理办法：https://www.ikjzd.com/home/109807
我和男同事在MSN上谈情说爱：http://www.30bags.com/a/253090.html
天猫海外发布跨境供销平台，首批600多广东服饰商家"云上新"：https://www.ikjzd.com/home/117647
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)