深度优先遍历，广度优先遍历实现对象的深拷贝

深度优先遍历

深度优先遍历（depth-first-search），是搜索算法的一种，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已探寻源节点到其他所有节点为止，如果还有未被发现的节点，则选择其中一个未被发现的节点为源节点并重复以上操作，直到所有节点都被探寻完成。
简单的说，dfs就是从图中的一个节点开始追溯，直到最后一个节点，然后回溯，继续追溯下一条路径，直到到达所有的节点，如此往复，直到没有路径为止。

dfs和bfs一般是用来解决图的遍历的，但是在这里，既然是前端，我是用dfs和bfs来遍历dom树。
下面采用栈的形式或者递归的形式实现：
dom节点

<div class="parent">
    <div class="c-1">
        <div class="c-1-1">
        </div>
        <div class="c-1-2">
        </div>
        <div class="c-1-3">
        </div>
        <div class="c-1-4">
        </div>
        <div class="c-1-5">
        </div>
    </div>
    <div class="c-2">
        <div class="c-2-1">
        </div>
        <div class="c-2-2">
        </div>
        <div class="c-2-3">
        </div>
        <div class="c-2-4">
            <div class="c-2-4-1">
            </div>
            <div class="c-2-4-2">
            </div>
            <div class="c-2-4-3">
            </div>
            <div class="c-2-4-4">
            </div>
            <div class="c-2-4-5">
            </div>
        </div>
        <div class="c-2-5">
        </div>
    </div>
    <div class="c-3">
    </div>
    <div class="c-4">
    </div>
</div>

dfs实现

var node = document.queryselectorall('.parent')[0];
    //递归写法
    function dfs1 (node, nodelist = []){
        if (node != null){
            nodelist.push(node);
            let children = node.children
            for(let i = 0; i < children.length; i++){
                dfs1(children[i], nodelist)
            }
        }
        return nodelist
    }
    let nodelist = dfs1(node);
    console.log(nodelist);
    //栈写法
    function dfs2(node){
        let nodelist = [];
        if (node){
            //栈  后进先出
            let stack = [];
            stack.push(node);
            while (stack.length) {
                let _node = stack.pop();
                nodelist.push(_node);
                let children = _node.children;
                //这样写是从右向左
                // for (let i = 0; i < children.length; i++) {
                //     stack.push(children[i]);
                // }
                //从左向右
                for (let i = children.length-1; i >= 0; i--) {
                    stack.push(children[i]);
                }
            }
        }
        return nodelist;
    }
    let nodelist2 = dfs2(node);
    console.log(nodelist2);

运行结果，上面dfs1和dfs2的结果是一样的

广度优先遍历

广度优先遍历（breadth-first-search）是从根节点开始，沿着图的宽度遍历节点，如果所有节点均被访问过，则算法终止，bfs 同样属于盲目搜索，一般用队列数据结构来辅助实现bfs。

还是采用上面的dom节点。bfs的写法如下。
代码采用队列的形式实现。

  var node = document.queryselectorall('.parent')[0];

    function bfs1(node, nodelist = []) {
        if (!node){
            return;
        }
        //队列 先进先出
        var sequeue = [];
        sequeue.push(node);
        while (sequeue.length){
            var _node = sequeue.shift();
            nodelist.push(_node)
            for(var i = 0; i < _node.children.length; i++){
                sequeue.push(_node.children[i])
            }
        }
        return nodelist
    }
    let nodelist = bfs1(node);
    console.log(nodelist);

结果如下

下面采用两种方式来实现对象深度克隆的实现。

dfs深度克隆

深度克隆要注意两个问题
1、环状数据问题：如果一个对象具有环状对象，比如obj.a.b.c === obj.a，就会使递归进入死循环，从而导致爆栈错误。
2、边界处理： 对象中不止原始类型，还存在如函数、set等数据类型，我们需要一一做处理。下面代码只是解决了对函数的复制。

let _tostring = object.prototype.tostring;
let map = {
    array: 'array',
    object: 'object',
    function: 'function',
    string: 'string',
    null: 'null',
    undefined: 'undefined',
    boolean: 'boolean',
    number: 'number'
}
function gettype(obj){
    return _tostring.call(obj).slice(8, -1)
}
function istypeof(obj, type){
    return map[type] && map[type] === gettype(obj)
}

//深度克隆
//深度优先遍历
/**
 * 
 * 解决三个问题 递归问题  环状数据问题   边界处理（比如函数，set等）
 */
const dfsdeepclone = function (obj, visitedarr = []){
    let _obj = {};
    if (istypeof(obj, 'array') || istypeof(obj, 'object')){
        let index = visitedarr.indexof(obj);
        if (index > -1){
            _obj = visitedarr[index]
        }
        else{
            visitedarr.push(obj)
            for (let key in obj){
                _obj[key] = dfsdeepclone(obj[key], visitedarr)
            }
        }
       
    }
    else if(istypeof(obj, 'function')){
        _obj = eval( '(' + obj.tostring() + ')')//处理函数
    }
    else{
        _obj = obj;//处理原始值
    }
    return _obj;
}
let testobj = {
    a: 1,
    b: {
        c: 1,
        d: 2
    },
    circle: null,
    e: function() {
        console.log(1);
    }
}
let clonetestobj = dfsdeepclone(testobj);
let clonetestobj2 = testobj;
console.log(clonetestobj);

console.log('经过深度克隆后的更改');
clonetestobj.b = {};//经过深度克隆后的更改
console.log(clonetestobj);
console.log(testobj);

clonetestobj2.b = {}; //引用的更改
console.log('引用的更改');
console.log(clonetestobj2);
console.log(testobj);

//环状数据
let testcircle = {
    a: 1,
    b: {
        c: 1,
        d: 2,
        circle: null,
    },
    e: function() {
        console.log(1);
    }
}
testcircle.b.circle = testcircle.b;
clonetestcircle = dfsdeepclone(testcircle);//不处理环问题是会爆栈的 进入死循环
console.log(clonetestcircle);

bfs深度克隆

let _tostring = object.prototype.tostring;
let map = {
    array: 'array',
    object: 'object',
    function: 'function',
    string: 'string',
    null: 'null',
    undefined: 'undefined',
    boolean: 'boolean',
    number: 'number'
}
function gettype(obj){
    return _tostring.call(obj).slice(8, -1)
}
function istypeof(obj, type){
    return map[type] && map[type] === gettype(obj)
}

//广度优先深度克隆， 利用队列的方式实现
//利用copyobj建立一个与原对象相同的数据结构， 遇到可处理的值（比如原始值，函数，就处理后赋值到相应的节点下）
const bfsdeepclone = function (obj, visitedarr = []){
    let copyobj = {};
    let sequeue = [obj];//进队列
    //同时copyobj也跟着一起进队列
    let copysequeue = [copyobj];
    while(sequeue.length){
        let _obj = sequeue.shift();
        let _copyobj = copysequeue.shift();
        if (istypeof(_obj, 'array') || istypeof(_obj, 'object')){
            for(item in _obj){
                let val = _obj[item];
                if (istypeof(val, 'object')){
                    let index = visitedarr.indexof(val)
                    if (~index){
                        //是环形数据
                        _copyobj[item] = visitedarr[index];
                    }
                    else{
                        //新的对象，给copyobj一个对应属性的空对象
                        sequeue.push(val);
                        _copyobj[item] = {};
                        copysequeue.push(_copyobj[item]);
                        visitedarr.push(val);
                    }
                    
                }
                else if (istypeof(val, 'array')){
                    sequeue.push(val);
                    _copyobj[item] = [];
                    copysequeue.push(_copyobj[item])
                }
                else if(istypeof(val, 'function')){
                    _copyobj[item] = eval( '(' + val.tostring() + ')');//处理函数
                }
                else{
                    _copyobj[item] = val;//处理原始值
                }
            }
        }
        else if(istypeof(obj, 'function')){
            _copyobj = eval( '(' + _obj.tostring() + ')');//处理函数
        }
        else{
            _copyobj = _obj;//处理原始值
        }
    }

    return copyobj

}

let testobj = {
    a: 1,
    b: {
        c: 1,
        d: 2
    },
    circle: null,
    e: function() {
        console.log(1);
    }
}
let clonetestobj = bfsdeepclone(testobj);
let clonetestobj2 = testobj;
console.log(clonetestobj);

//环状数据
let testcircle = {
    a: 1,
    b: {
        c: 1,
        d: 2,
        circle: null,
    },
    e: function () {
        console.log(1);
    }
}
testcircle.b.circle = testcircle.b;
clonetestcircle = bfsdeepclone(testcircle);//不处理环问题是会爆栈的 进入死循环
console.log(clonetestcircle);
/** 
 * 打印如下
{ a: 1, b: { c: 1, d: 2 }, circle: null, e: [function] }
{
    a: 1,
        b: { c: 1, d: 2, circle: { c: 1, d: 2, circle: [circular] } },
    e: [function]
}
*/