纯javascript实现dom树的遍历

时间:2022-08-25 13:27:50

二叉 DOM 树的遍历

[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. function Tree() {  
  2.         
  3.       var Node = function(key){  
  4.             this.key = key;  
  5.             this.left = null;  
  6.             this.right = null;  
  7.       }  
  8.       
  9.      root =null;  
  10. }  

前序遍历

<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">首先访问根结点,然后遍历左子树,最后遍历右子树</code>
[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. Tree.prototype.preOrderTraverse = function(callback){  
  2.     preOrder(root, callback);  
  3. }  
  4. var preOrder = function(node,callback){  
  5.     if(node !== null){  
  6.         callback(node.key);  
  7.         preOrder(node.left, callback);  
  8.         preOrder(node.right, callback);  
  9.     }  
  10. }  
  11.    
<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">修改为DOM二叉树:</code>

[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. var preOrder = function(node,callback) {  
  2.     callback(node);  
  3.     if(node.firstElementChild) {//先判断子元素节点是否存在  
  4.          this.preOrder(node.firstElementChild,callback);  
  5.     }  
  6.     if(node.lastElementChild) {  
  7.         this.preOrder(node.lastElementChild,callback);  
  8.     }  
  9. };  

中序遍历

<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">首先遍历左子树,然后访问根结点,最后遍历右子树。</code>
[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. Tree.prototype.inOrderTraverse = function(callback){  
  2.     inOrder(root, callback);  
  3. }  
  4. var inOrder = function(node,callback){  
  5.     if(node !== null){  
  6.         inOrder(node.left,callback);  
  7.         callback(node.key);  
  8.         inOrder(node.right, calback);  
  9.     }  
  10. }  
<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">修改为DOM二叉树:</code>
[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. var inOrder = function(node,callback){  
  2.     if(node.firstElementChild) {  
  3.     this.inOrder(node.firstElementChild);  
  4.     }  
  5.     callback(node);  
  6.     if(node.lastElementChild) {  
  7.     this.inOrder(node.lastElementChild);  
  8.     }  
  9. }  

后序遍历

<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">首先遍历左子树,然后遍历右子树,最后访问根结点。</code>
[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. Tree.prototype.postOrderTraverse = function(callback){  
  2.     postOrder(root, callback);  
  3. }  
  4. var postOrder = function(node,callback){  
  5.     if(node !== null){  
  6.         postOrder(node.left,callback);     
  7.         postOrder(node.right, calback);  
  8.         callback(node.key);  
  9.           
  10.     }  
  11. }  
<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">修改为DOM二叉树:</code>
[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. var postOrder = function(node,callback){  
  2.     if(node.firstElementChild) {  
  3.     this.postOrder(node.firstElementChild);  
  4.     }   
  5.     if(node.lastElementChild) {  
  6.     this.postOrder(node.lastElementChild);  
  7.     }  
  8.     callback(node);   
  9. }  


多叉 DOM 树的遍历


广度优先遍历

<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">首先遍历根节点,然后访问第一层节点,第二层节点,....,直到访问到最后一层。</code>
<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">借助于队列,用非递归的方式对多叉树进行遍历</code>
[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. Tree.prototype.BFSearch =  function(node,callback){  
  2.     var queue=[];  
  3.     while(node!=null){          
  4.            callback(node);  
  5.        if(node.children.length!=0){  
  6.         for (var i=0;i<node.children.length;i++){  
  7.             queue.push(node.children[i]);//借助于队列,暂存当前节点的所有子节点  
  8.         }   
  9.         }  
  10.             node=queue.shift();//先入先出,借助于数据结构:队列  
  11.     }         
  12. };  




深度优先遍历

<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">首先遍历根节点,然后沿着一条路径遍历到最深的一层,最后在逐层返回。</code>
<code style="font-family: 'Source Code Pro', Consolas, Menlo, Monaco, 'Courier New', monospace; font-size: 1em; color: inherit; padding: 0px; white-space: inherit; background: none;">借助于栈,实现多叉 DOM树 的深度优先遍历。</code>
[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. Tree.prototype.DFSearch =  function(node,callback){  
  2.         var stack=[];         
  3.         while(node!=null){  
  4.         callback(node);  
  5.         if(node.children.length!=0){  
  6.         for (var i=node.children.length-1;i>=0;i--){//按照相反的子节点顺序压入栈  
  7.             stack.push(node.children[i]);//将该节点的所有子节点压入栈  
  8.         }  
  9.         }  
  10.             node = stack.pop();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)        
  11.     }     
  12. };  



二叉 DOM 树的前序、中序、后序遍历,是深度优先遍历的特例

因此,参考深度优先遍历,借助栈,可以以非递归的方式,实现二叉 DOM 树的  前序、中序和后序遍历

非递归实现二叉 DOM 树的前序遍历

[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. Tree.prototype.preOrder = function(node,callback) {  
  2.         var stack=[];  
  3.         while(node!== null || stack.length!=0){  
  4.             while(node!==null){  
  5.                 stack.push(node);  
  6.                 callback.push(node);  
  7.                 node=node.firstElementChild;  
  8.             }  
  9.             node=stack.pop();  
  10.             node=node.lastElementChild;  
  11.         }  
  12.     };  

非递归实现二叉 DOM 树的中序遍历

[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. Tree.prototype.inOrder = function(node,callback) {  
  2.         var stack=[];  
  3.         while(node!== null || stack.length!=0){  
  4.             while(node!==null){  
  5.                 stack.push(node);  
  6.                 node=node.firstElementChild;  
  7.             }  
  8.             node=stack.pop();  
  9.             callback(node);  
  10.             node=node.lastElementChild;  
  11.         }  
  12.     };  

非递归实现二叉 DOM 树的后序遍历

  • 每个节点,都压入栈两次;
  • 在循环体中,每次弹出一个节点赋给node
  • 如果node仍然等于栈的头结点,说明node的孩子们还没有被操作过,应该把它的孩子们加入栈中
  • 否则,说明是第二次弹出该节点,访问node。
也就是说,第一次弹出,将node的孩子压入栈中,第二次弹出,访问node


[javascript] view plain copy 纯javascript实现dom树的遍历纯javascript实现dom树的遍历
  1. TreeWalker.prototype.postOrder = function(node,callback) {//非递归实现  
  2.     var stack=[];  
  3.         stack.push(node);  
  4.         stack.push(node);  
  5.     while(stack.length != 0)  
  6.     {  
  7.         node = stack.pop();  
  8.         if(stack.length != 0 && node==stack[stack.length-1])  
  9.         {  
  10.             if(node.lastElementChild) stack.push(node.lastElementChild), stack.push(node.lastElementChild);  
  11.             if(node.firstElementChild) stack.push(node.firstElementChild), stack.push(node.firstElementChild);  
  12.         }  
  13.         else  
  14.                 callback(node);  
  15.     }  
  16.            
  17. }