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

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

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

引言

搜索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