欢迎光临
我的个人博客网站

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


二叉树遍历

二叉树的遍历是指从根节点出发,按照某种顺序依次访问所有节点,而且只访问一次,二叉树的遍历方式很多,如果限制了从左到右的方式,那么主要有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 = 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))

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

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

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

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

步骤:

  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 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))

 

 

赞(0) 打赏
未经允许不得转载:张拓的天空 » 前端数据结构–二叉树先序、中序、后序 递归、非递归遍历
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏