javascript - 深度优先搜索的深拷贝对象

Question

我试图复制一个对象。我想用算法深度优先搜索来做到这一点。

function dfs(data) {
  let stack = [];
  let res = {};

  for (let key in data) {
    stack.push({ data: data[key], keyData: key });

    while (stack.length !== 0) {
      const first = stack.shift();

      if (typeof first.data === "object") {
        for (let key in first.data) {
          if (typeof first.data[key] === "object") {
            stack.push({ data: first.data[key], keyData: key });
          } else {
            res[first.parentKey] = first.keyData;
          }
        }
      } else {
        res[first.keyData] = first.data;
      }
    }
  }

  return res;
}

const data = {
  a: 1,
  b: 2,
  c: {
    d: 3,
    g: {
      e: 4,
      r: {
        y: 5,
      },
    },
  },
};

const newData = dfs(data);

data.c.g.e = 5000;
data.c.g.d = 90000;

console.log("Original data", data);
console.log("Copied data", newData);

我创建了一个函数，它将复制我的对象，而没有旧对象上的链接。我有一个问题，我的函数没有正确计算结果。我在哪里犯错？

标签： javascriptdepth-first-searchdeep-copy

Answer 1

深度优先搜索通常使用递归实现：

function dfs(data) {
  if (typeof data === 'object') {
    const result = {};
    
    for (let key in data) {
      result[key] = dfs(data[key]);
    }
    
    return result;
  }
  
  return data;
}

const data = {
  a: 1,
  b: 2,
  c: {
    d: 3,
    g: {
      e: 4,
      r: {
        y: 5,
      },
    },
  },
};

const newData = dfs(data);

data.c.g.e = 5000;
data.c.g.d = 90000;

console.log("Original data", data);
console.log("Copied data", newData);

这是一种迭代方法：

function dfs(data) {
  const result = {};
  const source = [['ROOT', data]];
  const target = [result];
  
  while (source.length) {
    const [k, v] = source.shift();
    const current = target.shift();
    const branch = typeof v === 'object';
    
    current[k] = branch ? {} : v;
    
    if (branch) {
      const entries = Object.entries(v);
      source.unshift(...entries);
      target.unshift(...Array(entries.length).fill(current[k]));
    }
  }
  
  return result.ROOT;
}

const data = {
  a: 1,
  b: 2,
  c: {
    d: 3,
    g: {
      e: 4,
      r: {
        y: 5,
      },
    },
  },
};
const newData = dfs(data);

data.c.g.e = 5000;
data.c.g.d = 90000;

console.log("Original data", data);
console.log("Copied data", newData);