利用深度/广度优先遍历手动实现JavaScript对象的深度拷贝

RobinTang 发布于2019-08-26 10:36 / 947人阅读

摘要：引言搜索对象的深度拷贝，往往会冒出转换和递归拷贝大法。但遇到大数据量，它们都有调用栈爆栈的风险今天，我们尝试利用树的利用深度广度优先遍历来实现对象的深度拷贝。以下代码在环境下全部测试通过。

引言

搜索JavaScript对象的深度拷贝，往往会冒出JSON转换和递归拷贝大法。但遇到大数据量，它们都有调用栈爆栈的风险
今天，我们尝试利用树的利用深度/广度优先遍历来实现对象的深度拷贝。以下代码在chrome环境下全部测试通过。

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

深度优先遍历对象，利用栈做中间节点缓存

     function deepCopy(orginObject) {
    if (orginObject == null || typeof orginObject !== "object") {
        return;
    }
    console.log("starting")
    const resultObject = {}
    const rootKey = Symbol("root");
    //深度遍历需要创建栈
    const stack = [];
    for (let key of Object.keys(orginObject)) {
        stack.push({
            key: key,//属性名
            value: orginObject[key],//value属性记录当前节点下属数据
            parent: resultObject//记录节点在resultObject中的位置
        })
    }

    while (stack.length) {
        const currentNode = stack.pop();
        const parent = currentNode.parent;
        const currentKey = currentNode.key;
        const currentValue = currentNode.value;
        //若是无下属对象，返回其值
        if (currentValue == null || typeof currentValue !== "object") {
            parent[currentKey] = currentValue;
        } else {
            //若下属值是对象，将子节点压入栈中
            parent[currentKey] = Object.prototype.toString.call(currentValue) === "[object Array]"?[]:{};
            for (let key of Object.keys(currentValue)) {
                console.log("loop:" + key, currentValue[key])
                stack.push({
                    key: key,
                    value: currentValue[key],
                    parent: parent[currentKey]
                })
            }
        }
    }
    return resultObject;
}
var copyObj = deepCopy({ a: { b: 1, d: { e: 6 } }, c: 3 });
console.log(copyObj);

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

广度优先遍历对象，利用队列做中间节点缓存

    function deepCopy(orginObject) {
    if (orginObject == null || typeof orginObject !== "object") {
        return;
    }
    console.log("starting")
    const resultObject = {}
    const rootKey = Symbol("root");
    //深度遍历需要创建栈
    const queue = [];
    for (let key of Object.keys(orginObject)) {
        queue.push({
            key: key,//属性名
            value: orginObject[key],//value属性记录当前节点下属数据
            parent: resultObject//记录节点在resultObject中的位置
        })
    }

    while (queue.length) {
        const currentNode = queue.shift();
        const parent = currentNode.parent;
        const currentKey = currentNode.key;
        const currentValue = currentNode.value;
        //若是无下属对象，返回其值
        if (currentValue == null || typeof currentValue !== "object") {
            parent[currentKey] = currentValue;
        } else {
            //若下属值是对象，将子节点压入栈中
            parent[currentKey] = Object.prototype.toString.call(currentValue) === "[object Array]"?[]:{};
            for (let key of Object.keys(currentValue)) {
                console.log("loop:" + key, currentValue[key])
                queue.push({
                    key: key,
                    value: currentValue[key],
                    parent: parent[currentKey]
                })
            }
        }
    }
    return resultObject;
}
var copyObj = deepCopy({ a: { b: 1, d: { e: 6 } }, c: 3 });
console.log(copyObj);

云服务器 GPU云服务器广度优先遍历图的深度遍历深度优先深度优先搜索

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106469.html

20190805-前端笔记-利用DFS广度优先遍历实现深拷贝

摘要：从这步开始，才是进行深度赋值进一步遍历每一个属性，进行赋值如果是，就直接以后赋值其他类型，直接赋值定义一些工具函数 let _toString = Object.prototype.toString // 类型库 let map = { array: Array, object: Object, function: Func...

shiweifu 2019-08-26 10:34 评论0 收藏0
浅谈JS的浅拷贝和深拷贝(递归和树遍历)

摘要：对象的特殊性因为对象的是通过指针仔细内存地址的，所以对象的拷贝不能像变量一般简单的赋值，对象的赋值只是将指针的地址赋值过去而已，修改属性值会对所有指向这个内存地址的对象的属性值都会被改变，见下面的例子变量赋值修改不会对造成影响对象赋值修改会 1.对象的特殊性因为对象的是通过指针仔细内存地址的，所以对象的拷贝不能像变量一般简单的赋值，对象的赋值只是将指针的地址赋值过去而已，修改属性值会...

cjie 2019-08-23 16:10 评论0 收藏0
JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

摘要：算法之深度优先遍历和广度优先遍历背景在开发页面的时候，我们有时候会遇到这种需求在页面某个节点中遍历，找到目标节点，我们正常做法是利用选择器，或者，但在本文，我们从算法的角度去查找节点，同时理解一下深度优先遍历和广度优先遍历的原理。 JS算法之深度优先遍历(DFS)和广度优先遍历(BFS) 背景在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom节点，...

roadtogeek 2019-08-23 16:33 评论0 收藏0
实现深度遍历和广度遍历(递归与非递归版本)

摘要：先画个树，然后解释何为深度，何为广度第一层子集第二层子集第二层子集第三层，子集第三层第四层图就不画太复杂了，最高四层的结构，如果换成的形式的话可以理解成第一层第二层先画个树，然后解释何为深度，何为广度第一层子集 | ...

Betta 2019-08-26 10:09 评论0 收藏0
深拷贝的终极探索（99%的人都不知道）

摘要：划重点，这是一道面试必考题，我靠这道题刷掉了多少面试者嘿嘿首先这是一道非常棒的面试题，可以考察面试者的很多方面，比如基本功，代码能力，逻辑能力，而且进可攻，退可守，针对不同级别的人可以考察不同难度，比如漂亮妹子就出题，要是个帅哥那就得上了，划重点，这是一道面试必考题，我靠这道题刷掉了多少面试者✧(≖ ◡ ≖✿)嘿嘿首先这是一道非常棒的面试题，可以考察面试者的很多方面，比如基本功，代...

qingshanli1988 2019-08-23 12:19 评论0 收藏0