JavaScript實現(xiàn)的DOM樹遍歷方法詳解【二叉DOM樹、多叉DOM樹】

更新時間：2018年05月07日 11:57:47 作者：ll_xiaohanqing_91

這篇文章主要介紹了JavaScript實現(xiàn)的DOM樹遍歷方法,結合實例形式詳細分析了二叉DOM樹、多叉DOM樹的前序、中序與后序遍歷,以及多叉樹深度優(yōu)先、廣度優(yōu)先等相關遍歷操作實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了JavaScript實現(xiàn)的DOM樹遍歷方法。分享給大家供大家參考，具體如下：

二叉 DOM 樹的遍歷

function Tree() {
   var Node = function(key){
      this.key = key;
      this.left = null;
      this.right = null;
   }
   root =null;
}

前序遍歷

首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹

Tree.prototype.preOrderTraverse = function(callback){
  preOrder(root, callback);
}
var preOrder = function(node,callback){
  if(node !== null){
    callback(node.key);
    preOrder(node.left, callback);
    preOrder(node.right, callback);
  }
}

修改為DOM二叉樹：

var preOrder = function(node,callback) {
  callback(node);
  if(node.firstElementChild) {//先判斷子元素節(jié)點是否存在
     this.preOrder(node.firstElementChild,callback);
  }
  if(node.lastElementChild) {
    this.preOrder(node.lastElementChild,callback);
  }
};

中序遍歷

首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。

Tree.prototype.inOrderTraverse = function(callback){
  inOrder(root, callback);
}
var inOrder = function(node,callback){
  if(node !== null){
    inOrder(node.left,callback);
    callback(node.key);
    inOrder(node.right, calback);
  }
}

修改為DOM二叉樹：

var inOrder = function(node,callback){
  if(node.firstElementChild) {
  this.inOrder(node.firstElementChild);
  }
  callback(node);
  if(node.lastElementChild) {
  this.inOrder(node.lastElementChild);
  }
}

后序遍歷

首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。

Tree.prototype.postOrderTraverse = function(callback){
  postOrder(root, callback);
}
var postOrder = function(node,callback){
  if(node !== null){
    postOrder(node.left,callback);
    postOrder(node.right, calback);
    callback(node.key);
  }
}

修改為DOM二叉樹：

var postOrder = function(node,callback){
  if(node.firstElementChild) {
  this.postOrder(node.firstElementChild);
  }
  if(node.lastElementChild) {
  this.postOrder(node.lastElementChild);
  }
  callback(node);
}

多叉 DOM 樹的遍歷

廣度優(yōu)先遍歷

首先遍歷根節(jié)點，然后訪問第一層節(jié)點，第二層節(jié)點，....,直到訪問到最后一層。

借助于隊列，用非遞歸的方式對多叉樹進行遍歷

Tree.prototype.BFSearch = function(node,callback){
  var queue=[];
  while(node!=null){
      callback(node);
    if(node.children.length!=0){
    for (var i=0;i<node.children.length;i++){
      queue.push(node.children[i]);//借助于隊列,暫存當前節(jié)點的所有子節(jié)點
    }
    }
      node=queue.shift();//先入先出，借助于數(shù)據(jù)結構：隊列
  }
};

深度優(yōu)先遍歷

首先遍歷根節(jié)點，然后沿著一條路徑遍歷到最深的一層，最后在逐層返回。

借助于棧,實現(xiàn)多叉 DOM樹的深度優(yōu)先遍歷。

Tree.prototype.DFSearch = function(node,callback){
    var stack=[];
    while(node!=null){
    callback(node);
    if(node.children.length!=0){
    for (var i=node.children.length-1;i>=0;i--){//按照相反的子節(jié)點順序壓入棧
      stack.push(node.children[i]);//將該節(jié)點的所有子節(jié)點壓入棧
    }
    }
      node = stack.pop();//彈出棧的子節(jié)點順序就是原來的正確順序(因為棧是先入后出的)
  }
};

二叉 DOM 樹的前序、中序、后序遍歷，是深度優(yōu)先遍歷的特例

因此，參考深度優(yōu)先遍歷，借助棧，可以以非遞歸的方式，實現(xiàn)二叉 DOM 樹的前序、中序和后序遍歷

非遞歸實現(xiàn)二叉 DOM 樹的前序遍歷

Tree.prototype.preOrder = function(node,callback) {
    var stack=[];
    while(node!== null || stack.length!=0){
      while(node!==null){
        stack.push(node);
        callback.push(node);
        node=node.firstElementChild;
      }
      node=stack.pop();
      node=node.lastElementChild;
    }
  };

非遞歸實現(xiàn)二叉 DOM 樹的中序遍歷

Tree.prototype.inOrder = function(node,callback) {
    var stack=[];
    while(node!== null || stack.length!=0){
      while(node!==null){
        stack.push(node);
        node=node.firstElementChild;
      }
      node=stack.pop();
      callback(node);
      node=node.lastElementChild;
    }
  };

非遞歸實現(xiàn)二叉 DOM 樹的后序遍歷

① 每個節(jié)點，都壓入棧兩次；
② 在循環(huán)體中，每次彈出一個節(jié)點賦給node
③ 如果node仍然等于棧的頭結點，說明node的孩子們還沒有被操作過，應該把它的孩子們加入棧中
④ 否則，說明是第二次彈出該節(jié)點，訪問node。

也就是說，第一次彈出，將node的孩子壓入棧中，第二次彈出，訪問node

TreeWalker.prototype.postOrder = function(node,callback) {//非遞歸實現(xiàn)
  var stack=[];
    stack.push(node);
    stack.push(node);
  while(stack.length != 0)
  {
    node = stack.pop();
    if(stack.length != 0 && node==stack[stack.length-1])
    {
      if(node.lastElementChild) stack.push(node.lastElementChild), stack.push(node.lastElementChild);
      if(node.firstElementChild) stack.push(node.firstElementChild), stack.push(node.firstElementChild);
    }
    else
        callback(node);
  }
}

更多關于JavaScript相關內(nèi)容感興趣的讀者可查看本站專題：《JavaScript操作DOM技巧總結》、《JavaScript錯誤與調試技巧總結》、《JavaScript數(shù)據(jù)結構與算法技巧總結》、《JavaScript遍歷算法與技巧總結》及《JavaScript數(shù)學運算用法總結》

希望本文所述對大家JavaScript程序設計有所幫助。

您可能感興趣的文章:

聊聊JavaScript如何實現(xiàn)繼承及特點
“繼承”是面向對象編程里面經(jīng)常提及到的概念，它的目的是實現(xiàn)代碼復用。這篇文章主要介紹了聊聊JavaScript如何實現(xiàn)繼承及特點，有興趣的可以了解一下。
2017-04-04
JS實現(xiàn)跟隨鼠標的鏈接文字提示框效果
這篇文章主要介紹了JS實現(xiàn)跟隨鼠標的鏈接文字提示框效果,涉及javascript鼠標事件及頁面元素樣式操作的相關技巧,非常簡單實用,需要的朋友可以參考下
2015-08-08
微信小程序下拉框組件使用方法詳解
這篇文章主要為大家詳細介紹了微信小程序下拉框組件的使用方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2018-12-12
判斷div滑動到底部的scroll實例代碼
下面小編就就為大家分享一篇判斷div滑動到底部的scroll實例代碼，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2017-11-11
ES6中如何使用Set和WeakSet
這篇文章主要為大家詳細介紹了ES6中如何使用Set和WeakSet的相關資料，感興趣的小伙伴們可以參考一下
2016-03-03
javascript函數(shù)的節(jié)流[throttle]與防抖[debounce]
這篇文章主要介紹了javascript函數(shù)的節(jié)流[throttle]與防抖[debounce ]，詳細的介紹了節(jié)流與防抖的原理和示例，具有一定的參考價值，有興趣的可以了解一下
2017-11-11
uniapp?實現(xiàn)自定義縮略滾動條效果
這篇文章主要介紹了uniapp?實現(xiàn)自定義縮略滾動條,本文通過示例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧
2024-08-08
HTML+JS模擬實現(xiàn)QQ下拉菜單效果
這篇文章主要為大家詳細介紹了如何利用HTML+JavaScript模擬實現(xiàn)QQ中的下拉菜單效果。文中的示例代碼講解詳細，感興趣的小伙伴可以學習一下
2022-05-05
JS前端的內(nèi)存處理的方法全面詳解
這篇文章主要為大家介紹了JS前端的內(nèi)存處理的方法全面詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2023-04-04
JavaScript實現(xiàn)跟隨鼠標移動的盒子
這篇文章主要為大家詳細介紹了JavaScript實現(xiàn)跟隨鼠標移動的盒子，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-01-01