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

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

小云云

發布： 2018-01-02 13:17:59

原創

1946 人瀏覽過

本文主要介紹了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 = 'blue';
  timer=setInterval(function(argument){
    i++;
    if(i登入後複製

核心程式碼如上，本來想寫深度優先遍歷和廣度優先遍歷。後來發現二元樹深度優先遍歷和先序遍歷相同。改日總結樹的BFS和DFS。

全部程式碼如下：

登入後複製

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登入後複製

由此可見，二叉樹的遍歷思想是一樣的。之前一直把JS看做是寫各種特效的語言，現在向來是too naive了。