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

程序员文章站 2022-07-06 20:54:34

本文实例讲述了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程序设计有所帮助。

上一篇： jquery实现左右轮播图效果

下一篇： vue2+el-menu实现路由跳转及当前项的设置方法实例

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

Python实现输入二叉树的先序和中序遍历，再输出后序遍历操作示例

PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

Python实现二叉树前序、中序、后序及层次遍历示例代码

PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

JavaScript实现二叉树定义、遍历及查找的方法详解

二叉树的先序遍历、中序遍历、后序遍历

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

python实现二叉树的层序、前序、中序、后序、之字形遍历

C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法

左神算法：分别用递归和非递归方式实现二叉树先序、中序和后序遍历（Java版）