首页 > 代码库 > js的搜索遍历精讲

js的搜索遍历精讲

搜索算法应该算是每种算法的重点与难点了,本文将讲解JavaScript中的各种常用的遍历算法;希望对大家有所帮助。

  技术分享

深度优先遍历顺序:1245367      广度优先遍历:1234567

1.深度优先遍历:分为递归与非递归两种方法。

  规则:从初始访问结点出发,我们知道初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点。总结起来可以这样说:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点.

具体算法表述如下:

  1. 访问初始结点v,并标记结点v为已访问。

  2. 查找结点v的第一个邻接结点w。

  3. 若w存在,则继续执行4,否则算法结束。

  4. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。

  5. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3

   递归算法

function traverseDF(node,nodeList){
    if(node){
        nodeList.push(node);
        for(var i=0;i<node.children.length;i++){
            traverseDF(node.children[i],nodeList);  
        }    
    }
}

  非递归算法

    function deepTraversal(node) {  
        var nodes = [];  
        if (node != null) {  
            var stack = [];  
            stack.push(node);  
            while (stack.length != 0) {  
                var item = stack.pop();  
                nodes.push(item);  
                var children = item.children;  
                for (var i = children.length - 1; i >= 0; i--)  
                    stack.push(children[i]);  
            }  
        }    
        return nodes;  
    }  

  非递归算法的效率会优于递归算法,因为递归算法在需要一次次的调用函数,而调用函数时需要比如准备函数内局部变量使用的空间、搞定函数的参数等等,这些事情每次调用函数都需要做,因此会产生额外开销导致递归效率偏低,所以逻辑上开销一致时递归的额外开销会多一些;非递归算法就是单独创建了一个”队列“,解决了递归算法的内存溢出问题。

 

2.广度优先算法,类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点。

具体算法表述如下:

  1. 访问初始结点v并标记结点v为已访问。

  2. 结点v入队列

  3. 当队列非空时,继续执行,否则算法结束。

  4. 出队列,取得队头结点u。

  5. 查找结点u的第一个邻接结点w。

  6. 若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:

    1). 若结点w尚未被访问,则访问结点w并标记为已访问。
    2). 结点w入队列
    3). 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。
  递归算法

function wideTraversal(node) {  
    var nodes = [];  
    var i = 0;  
    if (!(node == null)) {  
        nodes.push(node);  
        wideTraversal(node.nextElementSibling);  
        node = nodes[i++];  
        wideTraversal(node.firstElementChild);  
    }  
    return nodes;  
}

  非递归算法

 function wideTraversal(selectNode) {  
        var nodes = [];  
        if (selectNode != null) {  
            var queue = [];  
            queue.unshift(selectNode);  
            while (queue.length != 0) {  
                var item = queue.shift();  
                nodes.push(item);  
                var children = item.children;  
                for (var i = 0; i < children.length; i++)  
                    queue.push(children[i]);  
            }  
        }  
        return nodes;  
    }  

 

  前序,中序,后序遍历,前,后,中是相对于根节点而言的,前序及首先遍历根节点,中序及首先访问左子节点,然后才访问根节点,最后访问右子节点。

//前序遍历
function preOrder(node) {
    if (!(node == null)) {
        divList.push(node);
        preOrder(node.firstElementChild);
        preOrder(node.lastElementChild);
    }
}
//中序遍历
function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.firstElementChild);
        divList.push(node);
        inOrder(node.lastElementChild);
    }
}
//后序遍历
function postOrder(node) {
    if (!(node == null)) {
        postOrder(node.firstElementChild);
        postOrder(node.lastElementChild);
        divList.push(node);
    }
}

 

  

 

js的搜索遍历精讲