JS来搞定二叉DOM树的遍历

js构建一颗二叉树:

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

后序遍历

首先遍历左子树，然后遍历右子树，最后访问根结点。

    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();//弹出栈的子节点顺序就是原来的正确顺序(因为栈是先入后出的)      
    }   
};