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

以上就是本文的全部内容,希望对大家的学习有所帮助。

时间: 2016-03-17

JavaScript实现树的遍历算法示例【广度优先与深度优先】

本文实例讲述了JavaScript实现树的遍历算法.分享给大家供大家参考,具体如下: <script type="text/javascript"> var t = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]; //下面这段深度优先搜索方法出自Aimingoo的[JavaScript语言精髓与编程实践] var deepView = function(aTree,iNode) { (iNode in aTree)

JavaScript数据结构之二叉树的删除算法示例

本文实例讲述了JavaScript数据结构之二叉树的删除算法.分享给大家供大家参考,具体如下: 从二叉查找树上删除节点的操作复杂程度取决于删除哪个节点.如果删除没有子节点的节点就非常简单,如果节点只有一个子节点,不管是左子节点还是右子节点,就变得稍微有点复杂,如果节点包含两个子节点就最复杂. 如果待删除节点是叶子节点,那么只需要将从父节点指向它的链接指向null. 如果待删除节点只包含一个子节点,那么原本指向它的节点就得使其指向它的子节点. 如果待删除节点包含两个子节点,那么我们可以采用两种方式

JavaScript数据结构之二叉树的遍历算法示例

本文实例讲述了JavaScript数据结构之二叉树的遍历算法.分享给大家供大家参考,具体如下: 三种遍历的代码: function inOrder(node){//中序遍历 if(node!=null){ inOrder(node.left); document.write(node.show()+" "); inOrder(node.right); } } function preOrder(node){//先序遍历 if(node!=null){ document.write(no

JavaScript实现二叉树的先序、中序及后序遍历方法详解

本文实例讲述了JavaScript实现二叉树的先序.中序及后序遍历方法.分享给大家供大家参考,具体如下: 之前学数据结构的时候,学了二叉树的先序.中序.后序遍历的方法,并用C语言实现了,下文是用js实现二叉树的3种遍历,并以动画的形式展现出遍历的过程. 整个遍历过程还是采用递归的思想,原理很粗暴也很简单 先序遍历的函数: function preOrder(node){ if(!(node==null)){ divList.push(node); preOrder(node.firstEleme

JS实现的二叉树算法完整实例

本文实例讲述了JS实现的二叉树算法.分享给大家供大家参考,具体如下: <!DOCTYPE HTML> <head> <title>20130328BinaryTree</title> <metahttp-equiv="Content-Type" content="text/html; charset=utf-8" /> </head> <html> <body> <

JavaScript数据结构之二叉树的查找算法示例

本文实例讲述了JavaScript数据结构之二叉树的查找算法.分享给大家供大家参考,具体如下: 前面文章介绍了二叉树的遍历,现在谈谈在二叉树中进行查找.对二叉查找树来说,一般有以下三类查找:最大值,最小值和给定值. 查找最小值就是遍历左子树,直到找到最后一个结点,这是因为在二叉查找树中较小的值总是在左子节点上的. 代码如下: function getMin(){//查找最小值 var current=this.root;//指向根节点 while(current.left!=null){ cur

javascript实现二叉树遍历的代码

前言: 紧接着上篇 二叉树的javascript实现 ,来说一下二叉树的遍历. 本次一本正经的胡说八道,以以下这个二叉树为例子进行遍历: 接着是要引入二叉树实现的代码: function Node(data, left, right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() {

JavaScript数据结构之二叉树的计数算法示例

本文实例讲述了JavaScript数据结构之二叉树的计数算法.分享给大家供大家参考,具体如下: 二叉查找树的一个用途就是记录一组数据集中数据出现的次数.比如记录成绩的分布,给定一组考试成绩,如果未出现则加入树,如果已经出现则数量加一. 所以要修改Node对象,添加记录成绩出现次数加一,代码如下: function Node(data,left,right){ this.data=data; this.left=left; this.right=right; this.show=show; thi

JavaScript数据结构和算法之二叉树详解

二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct

javascript先序遍历DOM树的方法

DOM树由文档中的所有节点(元素节点.文本节点.注释节点等)所构成的一个树结构,DOM树的解析和构建是浏览器要实现的关键功能.既然DOM树是一个树结构,那么我们就可以使用遍历树结构的相关方法来对DOM树进行遍历,同时DOM2中的"Traversal"模块又提供了两种新的类型,从而可以很方便地实现DOM树的先序遍历. 注:本文中的5种方法都是对DOM的先序遍历方法(深度优先遍历),并且只关注Element类型. 1. 使用DOM1中的基础接口,递归遍历DOM树 DOM1中为基础类型Nod

javascript实现二叉树的代码

前言: 二叉树的特点(例图只是二叉树的一种情况,不要尝试用例图推理以下结论) 除了最下面一层,每个节点都是父节点,每个节点都有且最多有两个子节点: 除了嘴上面一层,每个节点是子节点,每个节点都会有一个父节点: 最上面一层的节点(即例图中的节点50)为根节点: 最下面一层的节点称为叶子节点,他们没有子节点: 左子节点的值 < 父节点的值 <= 右节点的值 1 节点的javascript实现 // 节点对象 function Node(data, left, right) { this.data

JS二叉树的简单实现方法示例

本文实例讲述了JS二叉树的简单实现方法.分享给大家供大家参考,具体如下: 今天学习了一下 二叉树的实现,在此记录一下 简单的二叉树实现,并且实现升序和降序排序输出 function Node(data , left,right){ this.data = data; this.left = left; this.right = right; this.show = show; function show(){ return this.data; } }; function Bst(){ this

json对象与数组以及转换成js对象的简单实现方法

JSON 语法规则 JSON 语法是 JavaScript 对象表示法语法的子集. •数据在名称/值对中 •数据由逗号分隔 •花括号保存对象 •方括号保存数组 JSON 对象 JSON 对象在花括号中书写: 对象可以包含多个名称/值对: { "firstName":"John" , "lastName":"Doe" } 这一点也容易理解,与这条 JavaScript 语句等价: firstName = "John&q

JS自定义对象创建与简单使用方法示例

本文实例讲述了JS自定义对象创建与简单使用方法.分享给大家供大家参考,具体如下: <html> <head> <title>js自定义函数</title> <meta charset="UTF-8"/> <script type="text/javascript"> //创建自定义对象 //方法一: // var obj=new Object(); //方法二 var obj={}; obj.n

JS正则匹配中文的方法示例

本文实例讲述了JS正则匹配中文的方法.分享给大家供大家参考,具体如下: 需求:使用JS正则的方式将字符串 "[微笑][撇嘴][发呆][得意][流泪]" 中的汉字进行匹配输出. 示例代码: <script> var pattern1 = /[\u4e00-\u9fa5]+/g; var pattern2 = /\[[\u4e00-\u9fa5]+\]/g; var contents = "[微笑][撇嘴][发呆][得意][流泪]"; content = c

AngularJS表格样式简单设置方法示例

本文实例讲述了AngularJS表格样式简单设置方法.分享给大家供大家参考,具体如下: 1.问题背景 AngularJS表格table,利用样式设置表格间隔色 2.实现源码 <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>AngularJS之表格设置样式</title> <link rel="stylesheet" h

JS对象的深度克隆方法示例

本文实例讲述了JS对象的深度克隆方法.分享给大家供大家参考,具体如下: js中创建的对象指向内存,所以在开发过程中,往往修改了一个对象的属性,会影响另外一个对象. 尤其是在angular框架中,dom是由数据驱动的,在增删改查对象的操作中,对象属性的继承关系是很让人头痛的! 我之前遇到的问题就是,在编辑页面,操作了对象数据,影响到了展示数据的展现! 我整理了两种深度克隆对象的方法,供大家参考! 首先var 一个假数据 复制代码 代码如下: var schedule = {"status"

Vue v-text指令简单使用方法示例

本文实例讲述了Vue v-text指令简单使用方法.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>v-text</title> <script type="text/javascript" src="https://cdn.bootc

PHP工厂模式简单实现方法示例

本文实例讲述了PHP工厂模式简单实现方法.分享给大家供大家参考,具体如下: 工厂模式是一种类,建立了一个工厂来根据所需来创建对象,这种方式在多态性编程中是很重要的,允许动态替换类,修改配置等. php示例代码如下: //-----------------------------工厂模式-------------------------// class A{ public $class; // public $class = $_GET['c']; //类名 public $method; //

JS实现的简单分页功能示例

本文实例讲述了JS实现的简单分页功能.分享给大家供大家参考,具体如下: HTML部分: <body onLoad="goPage(1,10);"> <table id="idData" width="70%"> <tr><td>user2</td><td>25</td><td>男</td><td>山西吕梁</td>&

vue.js使用3DES加密的方法示例

本文实例讲述了vue.js使用3DES加密的方法.分享给大家供大家参考,具体如下: 如何在VUE-CLI手脚架建立的工程中使用3des加密: npm install crypto-js --save-dev import CryptoJS from 'crypto-js' //DES加密 Pkcs7填充方式 encryptByDES(message, key){ const keyHex = CryptoJS.enc.Utf8.parse(key); const encrypted = Cryp