本文實例講述了JavaScript實現的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) {//先判斷子元素節點是否存在 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 樹的遍歷
廣度優先遍歷
首先遍歷根節點，然后訪問第一層節點，第二層節點，....,直到訪問到最后一層。
借助于隊列，用非遞歸的方式對多叉樹進行遍歷
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]);//借助于隊列,暫存當前節點的所有子節點 } } node=queue.shift();//先入先出，借助于數據結構：隊列 }};深度優先遍歷
首先遍歷根節點，然后沿著一條路徑遍歷到最深的一層，最后在逐層返回。
借助于棧,實現多叉 DOM樹 的深度優先遍歷。
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--){//按照相反的子節點順序壓入棧 stack.push(node.children[i]);//將該節點的所有子節點壓入棧 } } node = stack.pop();//彈出棧的子節點順序就是原來的正確順序(因為棧是先入后出的) }};二叉 DOM 樹的前序、中序、后序遍歷，是深度優先遍歷的特例
因此，參考深度優先遍歷，借助棧，可以以非遞歸的方式，實現二叉 DOM 樹的 前序、中序和后序遍歷
非遞歸實現二叉 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; } };非遞歸實現二叉 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; } };非遞歸實現二叉 DOM 樹的后序遍歷
① 每個節點，都壓入棧兩次；
② 在循環體中，每次彈出一個節點賦給node
③ 如果node仍然等于棧的頭結點，說明node的孩子們還沒有被操作過，應該把它的孩子們加入棧中
④ 否則，說明是第二次彈出該節點，訪問node。
也就是說，第一次彈出，將node的孩子壓入棧中，第二次彈出，訪問node
TreeWalker.prototype.postOrder = function(node,callback) {//非遞歸實現 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程序設計有所幫助。
新聞熱點
疑難解答
