纯javascript实现dom树的遍历

梦里梦外; 2022-07-15 14:16 187阅读 0赞

# 二叉 DOM 树的遍历 #

**\[javascript\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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.

## **\[javascript\]**  [view plain][]   [copy][view plain]    [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]  var preOrder = function(node,callback) \{        callback(node);        if(node.firstElementChild) \{ //先判断子元素节点是否存在             this.preOrder(node.firstElementChild,callback);        \}        if(node.lastElementChild) \{            this.preOrder(node.lastElementChild,callback);        \}    \};   ##

## 中序遍历 ##

<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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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. \}

**\[javascript\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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. \}

**\[javascript\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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. \}

[view plain]: http://blog.csdn.net/ll_xiaohanqing_91/article/details/51868134#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/1753792
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/1753792/fork