JS二叉树遍历(前序、中序、后序、深度优先、广度优先)

function Tree() {
   // 定义树结点
   var Node = function(element) {
      this.element = element;
      this.left = null;
      this.right = null;
   }
   // 定义根结点
   var root = null;
}

// 前序遍历 根左右 
Tree.prototype.preOrderTraverse = function(callback) {
    preOrder(root, callback);
  }

  var preOrder = function(node, callback) {
    if (node !== null) {
      callback(node.element);
      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);  
    }  
};  

// DOM的前序遍历 非递归方法 借助于栈
Tree.prototype.preOrder = function(node,callback) {  
        var stack=[];  
        while(node!== null || stack.length!=0){  
            while(node!==null){  
                stack.push(node);  
                callback(node);  
                node=node.firstElementChild;  
            }  
            node=stack.pop();  
            node=node.lastElementChild;  
        }  
    };  

// 中序遍历 左根右
Tree.prototype.inOrderTraverse = function(callback) {
    inOrder(root, callback);
  }
  var inOrder = function(node, callback) {
    if (node !== null) {
      inOrder(node.left, callback);
      callback(node);
      inOrder(node.right, callback);
    }
  }

// DOM中序遍历 左根右 递归方法
var inOrder = function(node, callback) {
    if (node.firstElementChild) {
      this.inOrder(node.firstElementChild,callback);
    }
    callback(node);
    if (node.lastElementChild) {
      this.inOrder(node.lastElementChild,callback);
    }
  }

// 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;  
        }  
    };  

// 后序遍历 左右根
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.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);
    }
  }

// 多叉树的遍历，广度优先遍历
// 层序遍历，借助队列，非递归方式
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(); //先入先出，借助于数据结构：队列  
    }
  };

// 多叉树的遍历，深度优先遍历
// 借助栈，首先遍历根节点，然后沿着一条路径遍历到最深的一层，最后在逐层返回
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(); //弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)        
    }
  };

参考链接：
JS实现DOM树的遍历