记住值路径的迭代深度优先遍历

Question

我需要有关迭代深度优先遍历算法具体实现的帮助。我有一个这样的对象（这只是一个例子，对象可能有更多的属性并且嵌套更深）：

const root = {
  a: 1,
  b: {
    c: {
      d: {
        e: 2,
        f: 3,
      }
    },
    g: [
      {
        h: 4,
        i: 5,
      },
      {
        j: 6,
        k: 7,
      }
    ]
  }
}

我需要的是一个可以遍历整个对象的函数和 return 一个像这样的数组：

[
  {"a": 1},
  {"b.c.d.e": 2},
  {"b.c.d.f": 3},
  {"b.g.0.h": 4},
  {"b.g.0.i": 5},
  {"b.g.1.j": 6},
  {"b.g.1.k": 7},
]

我设法创建了一种算法来解决我的问题，但最后还需要一个额外的步骤。算法的结果是这样的字符串数组：

[
  'a^1',
  'b.c.d.e^2',
  'b.c.d.f^3',
  'b.g.0.h^4',
  'b.g.0.i^5',
  'b.g.1.j^6',
  'b.g.1.k^7'
]

所以为了实现我想要的结果，我必须对我的算法结果进行一次完整的迭代，用 ^ 符号拆分字符串，然后基于它创建对象。

这是我需要帮助的部分 - 我如何才能 improve/change 我的解决方案而不需要执行最后一步？

function dft(root) {
  let stack = [];
  let result = [];
  const isObject = value => typeof value === "object";
  stack.push(root);
  while (stack.length > 0) {
    let node = stack.pop();
    if (isObject(node)) {
      Object.entries(node).forEach(([childNodeKey, childNodeValue]) => {
        if (isObject(childNodeValue)) {
          const newObject = Object.fromEntries(
            Object.entries(childNodeValue).map(([cnk, cnv]) => {
              return [`${childNodeKey}.${cnk}`, cnv];
            })
          );
          stack.push(newObject);
        } else {
          stack.push(`${childNodeKey}^${childNodeValue}`);
        }
      })
    } else {
      result.push(node);
    }
  }
  return result.reverse();
}

Answer 1

您可以将 childNodeKey childNodeValue 对作为对象直接推送到您的 result 数组。

改变

stack.push(`${childNodeKey}^${childNodeValue}`);

到

const newEntry = {}
newEntry[childNodeKey] = childNodeValue
result.push(newEntry);

或使用 ES2015 语法（您需要 browser compatibility 的转译器）

result.push({[childNodeKey]: childNodeValue});

完整功能：

const root = {
  a: 1,
  b: {
    c: {
      d: {
        e: 2,
        f: 3,
      }
    },
    g: [
      {
        h: 4,
        i: 5,
      },
      {
        j: 6,
        k: 7,
      }
    ]
  }
}

function dft(root) {
  let stack = [];
  let result = [];
  const isObject = value => typeof value === "object";
  stack.push(root);
  while (stack.length > 0) {
    let node = stack.pop();
    if (isObject(node)) {
      Object.entries(node).forEach(([childNodeKey, childNodeValue]) => {
        if (isObject(childNodeValue)) {
          const newObject = Object.fromEntries(
            Object.entries(childNodeValue).map(([cnk, cnv]) => {
              return [`${childNodeKey}.${cnk}`, cnv];
            })
          );
          stack.unshift(newObject);
        } else {
          const newEntry = {}
          newEntry[childNodeKey] = childNodeValue
          result.push({[childNodeKey]: childNodeValue});
        }
      })
    } else {
      result.push(node);
    }
  }
  return result;
}

console.log(dft(root))

Answer 2

我会在堆栈中保留对 <keys,value> 并且只在存储新创建的对象时创建一个字符串键：

function dft(obj) {
    let stack = []
    let res = []

    stack.push([[], obj])

    while (stack.length) {
        let [keys, val] = stack.pop()

        if (!val || typeof val !== 'object') {
            res.push({
                [keys.join('.')]: val
            })
        } else {
            Object.entries(val).forEach(p => stack.push([
                keys.concat(p[0]),
                p[1],
            ]))
        }
    }

    return res.reverse()
}

//

const root = {
  a: 1,
  b: {
    c: {
      d: {
        e: 2,
        f: 3,
      }
    },
    g: [
      {
        h: 4,
        i: 5,
      },
      {
        j: 6,
        k: 7,
      }
    ]
  }
}

console.log(dft(root))

Answer 3

正如您所说，您几乎完成了它。只需在将数组条目推入 result 之前将其设为对象即可。通过拆分 Array.prototype.split('^') 可以得到 'b.g.0.h^4' >>> ['b.g.0.h', '4']。所以，休息是小菜一碟:

if (isObject(node)) {
 ...
} else {
  const keyAndValue = node.split('^')
  // approach 1)
  // const key = keyAndValue[0]
  // const value = keyAndValue[1]
  // dynamic key setting
  // result.push({[key]: value});

  // approach 2)
  // or in short,
  // dynamic key setting
  result.push({[keyAndValue[0]]: keyAndValue[1]});
}

Answer 4

您可以使用一个堆栈，其中每个项目都有一个遍历子项的迭代器，以及到该点的路径：

function collect(root) {
    const Node = (root, path) => 
        ({ iter: Object.entries(root)[Symbol.iterator](), path });
    const result = [];
    const stack = [Node(root, "")];
    while (stack.length) {
        const node = stack.pop();
        const {value} = node.iter.next();
        if (!value) continue;
        stack.push(node);
        const [key, child] = value;
        const path = node.path ? node.path + "." + key : key;
        if (Object(child) !== child) result.push({ [path]: child });
        else stack.push(Node(child, path));
    }
    return result;
}

const root = {a:1,b:{c:{d:{e:2,f:3}},g:[{h:4,i:5},{j:6,k:7}]}};
console.log(collect(root));

Answer 5

我建议对您的代码进行最快的修复就是替换

  return result.reverse();

和

  return result.reverse()
    .map ((s, _, __, [k, v] = s .split ('^')) => ({[k]: v}));

但我也认为我们可以编写代码来更简单地做到这一点。函数 I use often 会将您的输入转换为如下内容：

[
  [["a"], 1],
  [["b", "c", "d", "e"], 2],
  [["b", "c", "d", "f"], 3],
  [["b", "g", 0, "h"], 4],
  [["b", "g", 0, "i"], 5],
  [["b", "g", 1, "j"], 6],
  [["b", "g", 1, "k"], 7]
]

然后一个相当简单的包装器可以将其转换为您的输出。它可能看起来像这样：

const pathEntries = (obj) =>
  Object (obj) === obj
    ? Object .entries (obj) .flatMap (
        ([k, x]) => pathEntries (x) .map (([p, v]) => [[Array.isArray(obj) ? Number(k) : k, ... p], v])
      ) 
    : [[[], obj]]

const transform = (o) => 
  pathEntries (o) 
    .map (([k, v]) => ({[k .join ('.')] : v}))

const root = {a: 1, b: {c: {d: {e: 2, f: 3, }}, g: [{h: 4, i: 5, }, {j: 6, k: 7}]}}

console .log (transform (root))

.as-console-wrapper {max-height: 100% !important; top: 0}

我不知道你的用例，但我会发现这个输出通常更有帮助：

{
  "a": 1, 
  "b.c.d.e": 2, 
  "b.c.d.f": 3, 
  "b.g.0.h": 4, 
  "b.g.0.i": 5, 
  "b.g.1.j": 6, 
  "b.g.1.k": 7
}

（即一个对象具有多个属性，而不是一组单个属性对象。）

我们几乎可以很容易地做到这一点，只需对 transform:

做一个小改动

const transform = (o) =>
  pathEntries (o) 
    .reduce ((a, [k, v]) => ((a[k .join ('.')] = v), a), {})

记住值路径的迭代深度优先遍历

Iterative depth-first traversal with remembering value's paths

javascript

algorithm

graph-theory

depth-first-search