网站首页  汉语字词  英语词汇  考试资料  写作素材  旧版资料

请输入您要查询的范文：

　

标题 JS中的二叉树遍历详解
范文
    这篇文章主要为大家详细介绍了JS中的二叉树遍历，何为二叉树，什么是二叉树的遍历，感兴趣的小伙伴们可以参考一下
    二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。
    这篇文章主要在JS中实现二叉树的遍历。
    一个二叉树的例子
    var tree = {
     value: 1,
     left: {
      value: 2,
      left: {
       value: 4
      }
     },
     right: {
      value: 3,
      left: {
       value: 5,
       left: {
        value: 7
       },
       right: {
        value: 8
       }
      },
      right: {
       value: 6
      }
     }
    }
    广度优先遍历
    广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。
    实现：
    <!--more-->
    使用数组模拟队列。首先将根节点归入队列。当队列不为空的时候，执行循环：取出队列的一个节点，如果该结点的左子树为非空，则将该结点的左子树入队列；如果该结点的右子树为非空，则将该结点的右子树入队列。
    （描述有点不清楚，直接看代码吧。）
    var levelOrderTraversal = function(node) { 
     if(!node) {  
      throw new Error('Empty Tree')
     } 
     var que = []
     que.push(node) 
     while(que.length !== 0) {
      node = que.shift()  
      console.log(node.value)  
      if(node.left) que.push(node.left)  
      if(node.right) que.push(node.right)
     }
    }
    递归遍历
    觉得用这几个字母表示递归遍历的三种方法不错：
    D：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。
    先序遍历：DLR
    中序遍历：LDR
    后序遍历：LRD
    顺着字母表示的意思念下来就是遍历的顺序了 ^ ^
    这3种遍历都属于递归遍历，或者说深度优先遍历（Depth-First Search，DFS），因为它总
    是优先往深处访问。
    先序遍历的递归算法：
    var preOrder = function (node) { 
     if (node) {  
      console.log(node.value);
      preOrder(node.left);
      preOrder(node.right);
     }
    }
    中序遍历的递归算法：
    var inOrder = function (node) { 
     if (node) {
      inOrder(node.left);  
      console.log(node.value);
      inOrder(node.right);
     }
    }
    后序遍历的递归算法：
    var postOrder = function (node) { 
     if (node) {
      postOrder(node.left);
      postOrder(node.right);  
      console.log(node.value);
     }
    }
    非递归深度优先遍历
    其实对于这些概念谁是属于谁的我也搞不太清楚。有的书里将二叉树的遍历只讲了上面三种递归遍历。有的分广度优先遍历和深度优先遍历两种，把递归遍历都分入深度遍历当中;有的分递归遍历和非递归遍历两种，非递归遍历里包括广度优先遍历和下面这种遍历。个人觉得怎么分其实并不重要，掌握方法和用途就好 ：）
    刚刚在广度优先遍历中使用的是队列，相应的，在这种不递归的深度优先遍历中我们使用栈。在JS中还是使用一个数组来模拟它。
    这里只说先序的：
    额，我尝试了描述这个算法，然而并描述不清楚，按照代码走一边你就懂了。
    var preOrderUnRecur = function(node) { 
     if(!node) {  
      throw new Error('Empty Tree')
     } 
     var stack = []
     stack.push(node) 
     while(stack.length !== 0) {
      node = stack.pop()  
      console.log(node.value)  
      if(node.right) stack.push(node.right)  
      if(node.left) stack.push(node.left)
     }
    }
    看了这一篇，找到了非递归后序的算法，所以在这里把非递归的遍历方法补充完整。
    非递归中序
    先把数的左节点推入栈，然后取出，再推右节点。
    var inOrderUnRecur = function(node) { 
     if(!node) {  
      throw new Error('Empty Tree')
     } 
     var stack = [] 
     while(stack.length !== 0 || node) {  
      if(node) {
       stack.push(node)
       node = node.left
      } else {
       node = stack.pop()   
       console.log(node.value)
       node = node.right
      }
     }
    }
    非递归后序(使用一个栈)
    这里使用了一个临时变量记录上次入栈/出栈的节点。思路是先把根节点和左树推入栈，然后取出左树，再推入右树，取出，最后取跟节点。
    var posOrderUnRecur = function(node) { 
     if(!node) {  
      throw new Error('Empty Tree')
     } 
     var stack = []
     stack.push(node) 
     var tmp = null
     while(stack.length !== 0) {
      tmp = stack[stack.length - 1]  
      if(tmp.left && node !== tmp.left && node !== tmp.right) {
       stack.push(tmp.left)
      } else if(tmp.right && node !== tmp.right) {
       stack.push(tmp.right)
      } else {   
       console.log(stack.pop().value)
       node = tmp
      }
     }
    }
    非递归后序(使用两个栈)
    这个算法的思路和上面那个差不多，s1有点像一个临时变量。
    var posOrderUnRecur = function(node) { 
     if(node) {  
      var s1 = []  
      var s2 = []
      s1.push(node)  
      while(s1.length !== 0) {
       node = s1.pop()
       s2.push(node)   
       if(node.left) {
        s1.push(node.left)
       }   
       if(node.right) {
        s1.push(node.right)
       }
      }  
      while(s2.length !== 0) {   
       console.log(s2.pop().value);
      }
     }
    }
    Morris遍历
    这个方法即不用递归也不用栈实现三种深度遍历，空间复杂度为O(1)（这个概念我也不是特别清楚org）
    （这三种算法我先放着，有空再研究）
    Morris先序:
    var morrisPre = function(head) { 
     if(!head) {  
      return
     } 
     var cur1 = head,
       cur2 = null
     while(cur1) {
      cur2 = cur1.left  
      if(cur2) {   
       while(cur2.right && cur2.right != cur1) {
        cur2 = cur2.right
       }   
       if(!cur2.right) {
        cur2.right = cur1    
        console.log(cur1.value)
        cur1 = cur1.left    
        continue
       } else {
        cur2.right = null
       }
      } else {   
        console.log(cur1.value)
      }
      cur1 = cur1.right
     }
    }
    Morris中序:
    var morrisIn = function(head) { 
     if(!head) {  
      return
     } 
     var cur1 = head,
       cur2 = null
     while(cur1) {
      cur2 = cur1.left  
      if(cur2) {   
       while(cur2.right && cur2.right !== cur1) {
        cur2 = cur2.right
       }   
       if(!cur2.right) {
        cur2.right = cur1
        cur1 = cur1.left    
        continue
       } else {
        cur2.right = null
       }
      }  
      console.log(cur1.value)
      cur1 = cur1.right
     }
    }
    Morris后序:
    var morrisPost = function(head) { 
     if(!head) {  
      return
     } 
     var cur1 = head,
       cur2 = null
     while(cur1) {
      cur2 = cur1.left  
      if(cur2) {   
       while(cur2.right && cur2.right !== cur1) {
        cur2 = cur2.right
       }   
       if(!cur2.right) {
        cur2.right = cur1
        cur1 = cur1.left    
        continue
       } else {
        cur2.right = null
        printEdge(cur1.left)
       }
      }
      cur1 = cur1.right
     }
     printEdge(head)
    }
    var printEdge = function(head) { 
    以上就是本文的全部内容，希望对大家的学习有所帮助。
随便看

　

在线学习网范文大全提供好词好句、学习总结、工作总结、演讲稿等写作素材及范文模板，是学习及工作的有利工具。

　

Copyright © 2002-2024 cuapp.net All Rights Reserved
更新时间：2025/5/23 0:13:45