深度优先与广度优先遍历DOM(递归与非递归)

若存在以下的DOM树结构我们改如何遍历所有的DOM节点;

<div id="root">
    <div>
        <p>
            <span></span>
        </p>
        <h1>

        </h1>
        <div>
            <p>
                <span></span>
            </p>
            <p>
                <span></span>
            </p>
        </div>
    </div>
    <div>
        <div>
            <span>
                <p>
                    <input type="text">
                </p>
            </span>
        </div>
    </div>
    <div>
            <input type="text">
    </div>
</div>

方法一：深度优先遍历算法

什么是深度优先算法？

这里以二叉树为例

若有二叉树

二叉树

深度优先遍历的结果：1 2 4 7 8 3 5 6 9 （若要深入了解，请自行百度”二叉树” “数据结构图” “c语言数据结构深度优先遍历算法”）

根据此算法编写JS代码

递归实现深度优先遍历

var nodes = [];
function DFS(node){
    var child = node.children;
    if(child){
        for(var i = 0; i < child.length;i++){
        	nodes.push(child[i]);
        	child[i].children && DFS(child[i]);
    	}
    }
    else return;
    
}
var root = document.getElementById('root');
DFS(document.getElementById('root'));
console.log(nodes);

递归实现深度优先遍历代码优化

var nodes = [];
function DFS(node){
    if(node){
        nodes.push(node);
        for(var i = 0;i < node.children.length;i++)
            DFS(node.children[i]);
    }
}
var root = document.getElementById('root');
DFS(root);
console.log(nodes);

闭包封装DFS

function DFS(node){
	var nodes = [];
	function fn(node){
		if(node){
            nodes.push(node);
            for(var i = 0;i < node.children.length;i++)
            fn(node.children[i]);
		}
	}
	fn(node);
	return nodes;
}
var root = document.getElementById('root');
console.log(DFS(root));

非递归实现深度优先遍历

function DFS(node){
    var nodes = [];//记录遍历到的节点
    if(node){
        var stark = [];//栈
        stark.push(node);
        while(stark.length){ //若栈不为空则一直出栈
            var temp = stark.pop();
            nodes.push(temp);
            if(temp.children)
                // for(var i = 0;i < temp.children.length;i++) //此法导致nodes中的元素顺序与页面上的顺序是相反的
                for(var i = temp.children.length-1;i >= 0 ;i--)
                    stark.push(temp.children[i]);//进栈
            else continue;
        }
    }
    return nodes;
}   
var root = document.getElementById('root');
console.log(DFS(root));

方法二：广度优先遍历算法

广度优先遍历二叉树结果:1 2 3 4 5 6 7 8 9（若要深入了解，请自行百度”二叉树” “数据结构图” “c语言数据结构广度优先遍历算法”）

根据此算法编写JS代码

递归实现广度优先算法

1	//最近头发掉的多了懂的自然懂

非递归实现广度优先算法

function BFS(node){
    var nodes = [];//记录获取到的节点
    if(node){
        var queue  = [];
        queue.push(node); //进队
        while(queue.length){  //只要队列不为空 就让其出队
            var temp = queue.shift();
            nodes.push(temp);
            if(temp.children)
                for(var i = 0;i < temp.children.length;i++)
                    queue.push(temp.children[i]);
            else continue;
        }
    }
    return nodes;
}

var root = document.getElementById('root');
console.log(BFS(root));