广度优先遍历、深度优先遍历
概念
广度优先遍历BFS是从根节点开始，一层一层的遍历，下一层的必须等上一层遍历完成才可以被访问。优先遍历的节点会被加入一个先进先出的队列中。
1、把根节点放到队列的末尾。
2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
3、遍历所有元素结束。
深度优先遍历DFS是从根节点开始，对每一个可能的分之路径深入到不能在深入为止，而且每个节点只能访问一次。
1、把根节点压入栈中。
2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
3、遍历所有元素结束。
深度优先采用的是堆栈的形式，即先进后出。
广度优先采用的是队列的实行，即先进先出。
例子
1、广度优先遍历
function getEmpty(o){if(Object.prototype.toString.call(o) == '[object Object]'){return {};}if(Object.prototype.toString.call(o) == '[object Array]'){return [];}return o;}function deepCopyBFS(origin){let queue = [];let map = new WeakMap();let target = getEmpty(origin);if(target!=origin){queue.push([origin, target]);map.set(origin, target);}while(queue.length){let [ori, tar] = queue.shift();console.log(ori);for(let key in ori){if(map.get(ori[key])){tar[key] = map.get(ori[key]);continue;}tar[key] = getEmpty(ori[key]);if(tar[key]!==ori[key]){queue.push([ori[key],tar[key]]);map.set(ori[key], tar[key]);}}}return target;}let sourceObj = { a: { a1: 'a1', a2: 'a2', a3: { aa1: 'aa1' } }, b: { b1: 'b1' } };deepCopyBFS(sourceObj);
2、深度优先遍历
function getEmpty(o){if(Object.prototype.toString.call(o) == '[object Object]'){return {};}if(Object.prototype.toString.call(o) == '[object Array]'){return [];}return o;}function deepCopyDFS(origin){let stack = [];let map = new WeakMap();let target = getEmpty(origin);if(target!==origin){stack.push([origin, target]);map.set(origin, target);}while(stack.length){let [ori, tar] = stack.pop();console.log(ori);for(let key in ori){if(map.get(ori[key])){tar[key] = map.get(ori[key]);continue;}tar[key] = getEmpty(ori[key]);if(tar[key]!==ori[key]){stack.push([ori[key], tar[key]]);map.set(ori[key], tar[key]);}}}return target;}