JavaScript如何實現(xiàn)二叉樹的先序、中序及后序遍歷方法

發(fā)布時間：2021-04-13 11:41:53 來源：億速云閱讀：309 作者：小新欄目：web開發(fā)

這篇文章主要介紹了JavaScript如何實現(xiàn)二叉樹的先序、中序及后序遍歷方法，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

具體如下：

之前學數(shù)據(jù)結構的時候，學了二叉樹的先序、中序、后序遍歷的方法，并用C語言實現(xiàn)了，下文是用js實現(xiàn)二叉樹的3種遍歷，并以動畫的形式展現(xiàn)出遍歷的過程。

整個遍歷過程還是采用遞歸的思想，原理很粗暴也很簡單

先序遍歷的函數(shù)：

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

中序遍歷的函數(shù)：

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

后序遍歷的函數(shù)：

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

顏色變化函數(shù)：

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

核心代碼如上，本來想寫深度優(yōu)先遍歷和廣度優(yōu)先遍歷。后來發(fā)現(xiàn)二叉樹深度優(yōu)先遍歷和先序遍歷相同。改日總結一下樹的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);
  }
}
/*顏色變化函數(shù)*/
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看做是寫各種特效的語言，現(xiàn)在向來是too naive了。

感謝你能夠認真閱讀完這篇文章，希望小編分享的“JavaScript如何實現(xiàn)二叉樹的先序、中序及后序遍歷方法”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業(yè)資訊頻道，更多相關知識等著你來學習!

向AI問一下細節(jié)

JavaScript如何實現(xiàn)二叉樹的先序、中序及后序遍歷方法

猜你喜歡

最新資訊

相關推薦

相關標簽

JavaScript如何實現(xiàn)二叉樹的先序、中序及后序遍歷方法