本文详细解析JavaScript中DOM树的多种遍历策略，涵盖二叉树与多叉树场景。重点阐述前序、中序、后序遍历原理，并深入讲解如何利用队列实现多叉树的广度优先搜索，以及借助栈结构实现递归与非递归的深度优先遍历，包含具体的代码逻辑与算法步骤。
引言
本文通过具体实例介绍JavaScript中DOM树的遍历实现方式，旨在为开发者提供实用的参考代码与技术解析。
二叉DOM树遍历
二叉DOM树的遍历策略
function Tree() {
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
root =null;
}
前序遍历的核心逻辑是：首先访问根节点，接着递归遍历左子树，最后遍历右子树。
将上述逻辑适配到DOM二叉树结构中，需调整节点访问方式。
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);
}
}
var preOrder = function(node,callback) {
callback(node);
if(node.firstElementChild) {//先判断子元素节点是否存在
this.preOrder(node.firstElementChild,callback);
}
if(node.lastElementChild) {
this.preOrder(node.lastElementChild,callback);
}
};
中序遍历的执行顺序为：先遍历左子树，随后访问根节点，最后遍历右子树。
针对DOM二叉树的中序遍历，需根据DOM节点特性调整递归逻辑。
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);
}
}
var inOrder = function(node,callback){
if(node.firstElementChild) {
this.inOrder(node.firstElementChild);
}
callback(node);
if(node.lastElementChild) {
this.inOrder(node.lastElementChild);
}
}
后序遍历的规则是：依次遍历左子树和右子树，最后访问根节点。
将后序遍历应用于DOM二叉树时，需确保子节点处理完毕后再访问当前节点。
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);
}
}
var postOrder = function(node,callback){
if(node.firstElementChild) {
this.postOrder(node.firstElementChild);
}
if(node.lastElementChild) {
this.postOrder(node.lastElementChild);
}
callback(node);
}
多叉DOM树遍历
多叉DOM树的遍历方法
广度优先遍历（BFS）的策略是：从根节点开始，逐层访问节点，即先访问第一层，再访问第二层，依此类推，直至最后一层。
实现多叉树的广度优先遍历，通常借助队列数据结构进行非递归处理。
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();//先入先出，借助于数据结构：队列
}
};
深度优先遍历（DFS）的策略是：从根节点出发，沿一条路径一直遍历到最深的一层，然后逐层回溯返回。
对于多叉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仍等于栈顶元素，说明其子节点尚未处理，需将子节点入栈；④ 否则，表明是第二次弹出该节点，此时执行访问操作。
简而言之，第一次弹出节点时将其子节点压入栈，第二次弹出时再访问该节点。
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相关内容感兴趣的读者可查看本站专题：《JavaScript操作DOM技巧总结》、《JavaScript错误与调试技巧总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript遍历算法与技巧总结》及《JavaScript数学运算用法总结》
希望本文关于JavaScript程序设计的阐述能对大家有所帮助。