欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

JS二叉树的先序中序及后序遍历实现方法

程序员文章站 2022-04-01 16:09:54
...

这次给大家带来JS二叉树的先序中序及后序遍历实现方法,JS二叉树先序中序及后序遍历实现方法的注意事项有哪些,下面就是实战案例,一起来看一下。

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

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

先序遍历的函数:

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

中序遍历的函数:

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

后序遍历的函数:

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

颜色变化函数:

function changeColor(){
  var i=0;
  pList[i].style.backgroundColor = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i<pList.length){
      pList[i-1].style.backgroundColor="#fff";
      pList[i].style.backgroundColor="blue";
    }
    else{
      pList[pList.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>
<p class="root">
  <p class="child_1">
    <p class="child_2">
      <p class="child_3"></p>
      <p class="child_3"></p>
    </p>
    <p class="child_2">
      <p class="child_3"></p>
      <p class="child_3"></p>
    </p>
  </p>
  <p class="child_1">
    <p class="child_2">
      <p class="child_3"></p>
      <p class="child_3"></p>
    </p>
    <p class="child_2">
      <p class="child_3"></p>
      <p class="child_3"></p>
    </p>
  </p>
</p>
<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],
  pList = [],
  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)){
    pList.push(node);
    preOrder(node.firstElementChild);
    preOrder(node.lastElementChild);
  }
}
/*中序遍历*/
function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.firstElementChild);
    pList.push(node);
    inOrder(node.lastElementChild);
  }
}
/*后序遍历*/
function postOrder(node) {
  if (!(node == null)) {
    postOrder(node.firstElementChild);
    postOrder(node.lastElementChild);
    pList.push(node);
  }
}
/*颜色变化函数*/
function changeColor(){
  var i=0;
  pList[i].style.backgroundColor = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i<pList.length){
      pList[i-1].style.backgroundColor="#fff";
      pList[i].style.backgroundColor="blue";
    }
    else{
      pList[pList.length-1].style.backgroundColor="#fff";
    }
  },500)
}
function reset(){
  pList=[];
  clearInterval(timer);
  var ps=document.getElementsByTagName("p");
  for(var i=0;i<ps.length;i++){
    ps[i].style.backgroundColor="#fff";
  }
}

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

相信看了本文案例你已经掌握了方法,更多精彩请关注其它相关文章!

推荐阅读:

touch事件如何获取滑动距离长度

JS+H5+C3实现弹出窗口

以上就是JS二叉树的先序中序及后序遍历实现方法的详细内容,更多请关注其它相关文章!