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

本文实例讲述了JavaScript实现二叉树的先序、中序及后序遍历方法。分享给大家供大家参考,具体如下:

之前学数据结构的时候,学了二叉树的先序、中序、后序遍历的方法,并用C语言实现了,下文是用js实现二叉树的3种遍历,并以动画的形式展现出遍历的过程。

整个遍历过程还是采用递归的思想,原理很粗暴也很简单

先序遍历的函数:

function preOrder(node){
  if(!(node==null)){
    divList.push(node);
    preOrder(node.firstElementChild);
    preOrder(node.lastElementChild);
  }
}

中序遍历的函数:

function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.firstElementChild);
    divList.push(node);
    inOrder(node.lastElementChild);
  }
}

后序遍历的函数:

function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.firstElementChild);
    postOrder(node.lastElementChild);
    divList.push(node);
  }
}

颜色变化函数:

function changeColor(){
  var i=0;
  divList[i].style.backgroundColor = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i<divList.length){
      divList[i-1].style.backgroundColor="#fff";
      divList[i].style.backgroundColor="blue";
    }
    else{
      divList[divList.length-1].style.backgroundColor="#fff";
    }
  },500)
}

核心代码如上,本来想写深度优先遍历和广度优先遍历。后来发现二叉树深度优先遍历和先序遍历相同。改日总结一下树的BFS和DFS。

全部代码如下:

<!DOCTYPE html>
<html>
<head lang="en">
  <meta charset="UTF-8">
  <title></title>
  <style>
    .root{
      display: flex;
      padding: 20px;
      width: 1000px;
      height: 300px;border: 1px solid #000000;
      margin: 100px auto;
      margin-bottom: 10px;
      justify-content: space-between;
    }
    .child_1{
      display: flex;
      padding: 20px;
      width: 450px;
      height: 260px;border: 1px solid red;
      justify-content: space-between;
    }
    .child_2{
      display: flex;
      padding: 20px;
      width: 170px;
      height: 220px;border: 1px solid green;
      justify-content: space-between;
    }
    .child_3{
      display: flex;
      padding: 20px;
      width: 35px;
      height: 180px;border: 1px solid blue;
      justify-content: space-between;
    }
    input{
      margin-left: 100px;
      width: 60px;
      height: 40px;
      font:20px italic;
    }
  </style>
</head>
<body>
<div class="root">
  <div class="child_1">
    <div class="child_2">
      <div class="child_3"></div>
      <div class="child_3"></div>
    </div>
    <div class="child_2">
      <div class="child_3"></div>
      <div class="child_3"></div>
    </div>
  </div>
  <div class="child_1">
    <div class="child_2">
      <div class="child_3"></div>
      <div class="child_3"></div>
    </div>
    <div class="child_2">
      <div class="child_3"></div>
      <div class="child_3"></div>
    </div>
  </div>
</div>
<input type="button" value="先序">
<input type="button" value="中序">
<input type="button" value="后序">
<script type="text/javascript" src="遍历.js"></script>
</body>
</html>

js:

/**
 * Created by hp on 2016/12/22.
 */
var btn = document.getElementsByTagName('input'),
  preBtn = btn[0],
  inBtn = btn[1],
  postBtn = btn[2],
  treeRoot = document.getElementsByClassName('root')[0],
  divList = [],
  timer = null;
window.onload=function(){
  preBtn.onclick = function () {
    reset();
    preOrder(treeRoot);
    changeColor();
  }
  inBtn.onclick = function () {
    reset();
    inOrder(treeRoot);
    changeColor();
  }
  postBtn.onclick = function () {
    reset();
    postOrder(treeRoot);
    changeColor();
  }
}
/*先序遍历*/
function preOrder(node){
  if(!(node==null)){
    divList.push(node);
    preOrder(node.firstElementChild);
    preOrder(node.lastElementChild);
  }
}
/*中序遍历*/
function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.firstElementChild);
    divList.push(node);
    inOrder(node.lastElementChild);
  }
}
/*后序遍历*/
function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.firstElementChild);
    postOrder(node.lastElementChild);
    divList.push(node);
  }
}
/*颜色变化函数*/
function changeColor(){
  var i=0;
  divList[i].style.backgroundColor = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i<divList.length){
      divList[i-1].style.backgroundColor="#fff";
      divList[i].style.backgroundColor="blue";
    }
    else{
      divList[divList.length-1].style.backgroundColor="#fff";
    }
  },500)
}
function reset(){
  divList=[];
  clearInterval(timer);
  var divs=document.getElementsByTagName("div");
  for(var i=0;i<divs.length;i++){
    divs[i].style.backgroundColor="#fff";
  }
}

由此可见,二叉树的遍历思想是一样的。之前一直把JS看做是写各种特效的语言,现在向来是too naive了。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

(0)

相关推荐

  • 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先序遍历DOM树的方法

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

  • 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 } } } 广度优先遍历 广度优先遍历是从二叉树

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

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

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

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

  • javascript实现二叉树的代码

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

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

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

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

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

  • 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数据结构之二叉树的遍历算法.分享给大家供大家参考,具体如下: 三种遍历的代码: 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

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

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

  • 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

随机推荐