JavaScript實作二元樹的先序、中序及後序遍歷方法-js教程-PHP中文網

首頁

web前端

js教程

JavaScript實作二元樹的先序、中序及後序遍歷方法

小云云

Jan 02, 2018 pm 01:17 PM

javascriptjs方法

本文主要介紹了JavaScript實作二元樹的先序、中序及後序遍歷方法,結合實例形式總結分析了javascript二元樹的先序、中序及後序遍歷實現方法與相關操作注意事項,需要的朋友可以參考下，希望能幫助大家。

本文實例講述了JavaScript實作二元樹的先序、中序及後序遍歷方法。分享給大家供大家參考，具體如下：

之前學資料結構的時候，學了二元樹的先序、中序、後序遍歷的方法，並用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 = &#39;blue&#39;;
  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 = &#39;blue&#39;;
  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由此可見，二叉樹的遍歷思想是一樣的。之前一直把JS看做是寫各種特效的語言，現在向來是too naive了。 
相關推薦：
php中關於完全二元樹的定義方法詳解
Java最小二元樹堆排序的實作方法 
js實作資料結構: 樹與二元樹,二元樹的遍歷與基本運算方法
以上是JavaScript實作二元樹的先序、中序及後序遍歷方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

Python vs. JavaScript：開發環境和工具Apr 26, 2025 am 12:09 AM

Python和JavaScript在開發環境上的選擇都很重要。 1)Python的開發環境包括PyCharm、JupyterNotebook和Anaconda，適合數據科學和快速原型開發。 2)JavaScript的開發環境包括Node.js、VSCode和Webpack，適用於前端和後端開發。根據項目需求選擇合適的工具可以提高開發效率和項目成功率。

JavaScript是用C編寫的嗎？檢查證據Apr 25, 2025 am 12:15 AM

是的，JavaScript的引擎核心是用C語言編寫的。 1）C語言提供了高效性能和底層控制，適合JavaScript引擎的開發。 2）以V8引擎為例，其核心用C 編寫，結合了C的效率和麵向對象特性。 3）JavaScript引擎的工作原理包括解析、編譯和執行，C語言在這些過程中發揮關鍵作用。

JavaScript的角色：使網絡交互和動態Apr 24, 2025 am 12:12 AM

JavaScript是現代網站的核心，因為它增強了網頁的交互性和動態性。 1)它允許在不刷新頁面的情況下改變內容，2)通過DOMAPI操作網頁，3)支持複雜的交互效果如動畫和拖放，4)優化性能和最佳實踐提高用戶體驗。

C和JavaScript：連接解釋Apr 23, 2025 am 12:07 AM

C 和JavaScript通過WebAssembly實現互操作性。 1）C 代碼編譯成WebAssembly模塊，引入到JavaScript環境中，增強計算能力。 2）在遊戲開發中，C 處理物理引擎和圖形渲染，JavaScript負責遊戲邏輯和用戶界面。

從網站到應用程序：JavaScript的不同應用Apr 22, 2025 am 12:02 AM

JavaScript在網站、移動應用、桌面應用和服務器端編程中均有廣泛應用。 1)在網站開發中，JavaScript與HTML、CSS一起操作DOM，實現動態效果，並支持如jQuery、React等框架。 2)通過ReactNative和Ionic，JavaScript用於開發跨平台移動應用。 3)Electron框架使JavaScript能構建桌面應用。 4)Node.js讓JavaScript在服務器端運行，支持高並發請求。

Python vs. JavaScript：比較用例和應用程序Apr 21, 2025 am 12:01 AM

Python更適合數據科學和自動化，JavaScript更適合前端和全棧開發。 1.Python在數據科學和機器學習中表現出色，使用NumPy、Pandas等庫進行數據處理和建模。 2.Python在自動化和腳本編寫方面簡潔高效。 3.JavaScript在前端開發中不可或缺，用於構建動態網頁和單頁面應用。 4.JavaScript通過Node.js在後端開發中發揮作用，支持全棧開發。