如何正确实现此 JavaScript (TypeScript) 树递归函数？

Question

我正在尝试编写递归函数的代码，但我很挣扎，我希望有人能帮助我朝着正确的方向前进。我相信这将被视为“树递归”。

这是一个简单的例子，用于说明数据和我正在尝试做的事情。显然，真实的数据更复杂...

基本上，我从一个包含单个对象数组的数组开始，如下所示，其中任何对象中的 prop2 可以是有效字符串或空字符串...

[
    [
        { prop1: "abc", prop2: "" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ]
]

我的算法需要查看上面的数组并遍历对象。一旦在 prop2 中遇到空字符串的对象，它需要将数组克隆 3 次，并用三个不同的值 (one/two/three) 替换该对象中的空字符串（并且只有该对象）（one/two/three）。 ..

[
    [
        { prop1: "abc", prop2: "one" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ],
    [
        { prop1: "abc", prop2: "two" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ],
    [
        { prop1: "abc", prop2: "three" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ]
]

然后算法再次开始，除了输入是这个包含三个数组的新数组。

所以在第二次迭代中，三个数组中的每一个都将被克隆三次，空字符串将以相同的方式被替换。

这个简单示例的最终结果将是一个包含九个数组的数组。

如果数组中有更多 prop2 值为空的对象，就会有更多的迭代。

基本上，我正在获取一个对象数组，其中一些道具是空字符串，并将该特定道具值“扩展”到“一”/“二”/“三”的每个排列

我知道这是递归的理想问题，但我在计算代码时遇到了问题。

我认为“基本情况”可能是我有一个对象数组并且 none 个对象具有空字符串的属性。那种情况会 return 那个数组。

除了用三个新创建的变体调用同一个函数三次之外，我不知道其他情况会是什么样子。我也不知道这个案例应该是什么returning。

我在网上找不到与我正在尝试做的类似的参考示例。

编辑：看看递归响应，即使它们都有效，很明显递归解决方案并不像我想象的那么简单。非递归答案实际上是最好的答案。

Answer 1

我推荐这个 non-reclusive 解决方案，它可以满足您的 end-result 要求：

const myTree = [
    [
        { prop1: "abc", prop2: "" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ]
];

let nodesWithEmptyStrings = myTree.filter(n=> !!n.find(l=> l.prop2===""));
while(nodesWithEmptyStrings.length > 0) {
  nodesWithEmptyStrings.forEach(n => {
    const firstEmptyStringLeaveIndex = n.findIndex(l=> l.prop2==="");
    n[firstEmptyStringLeaveIndex].prop2 = "one";
    const copy1 = JSON.parse(JSON.stringify(n));
    copy1[firstEmptyStringLeaveIndex].prop2 = "two";
    myTree.push(copy1);
    
    const copy2 = JSON.parse(JSON.stringify(n));
    copy2[firstEmptyStringLeaveIndex].prop2 = "three";
    myTree.push(copy2);
  });
  nodesWithEmptyStrings = myTree.filter(n=> !!n.find(l=> l.prop2===""));
}

document.getElementById('result').innerText = JSON.stringify(myTree, null, 2);

<pre id="result"></pre>

Answer 2

是的，您可以使用递归来做到这一点。基本原理是修改数组，然后检查是否需要再修改一些，如果是的话，return用新数组调用函数的结果。

这是一个例子：

const fillers = ['one', 'two', 'three'];
const propToCheck = 'prop2';

function recursion(arr) {
  const mod = arr.reduce((a, c) => {
    const found = c.find(v => !v[propToCheck]);
    if (found) {
      const tmp = c.filter(v => v !== found);
      return [...a, ...fillers.map(filler => [...tmp, { ...found, [propToCheck]: filler }])];
    }
    return [...a, c];
  }, []);
  const notDone = mod.some(v => v.some(o => !o[propToCheck]))
  if (notDone) {
    return recursion(mod);
  }
  return mod;
}

const result = recursion([
    [
        { prop1: "abc", prop2: "" },
        { prop1: "def", prop2: "one" },
        { prop1: "ghi", prop2: "" }
    ]
]);

console.log(result);

Answer 3

我不知道这是否是一个直觉上我想用递归来解决的问题，但是这个既接受替换又接受什么键来检查空字符串作为参数的通用函数可以工作（使用 es6+ 语法和具有大量解构的功能）：

const substitute = (data, index, keyToCheck, substitutes) => {
  const indexOfObjectWithEmptyKeyToCheck = data[index].findIndex(obj => obj[keyToCheck] === "")
    if(indexOfObjectWithEmptyKeyToCheck === -1) {
        if(index === data.length - 1)
            return data
        else
            return substitute(data, index + 1, keyToCheck, substitutes)
    }
    else {
        return substitute(
            [
                ...data.slice(0, index),
                ...(substitutes.map(
                    substitute => [
                        ...data[index].slice(0, indexOfObjectWithEmptyKeyToCheck),
                        { ...data[index][indexOfObjectWithEmptyKeyToCheck], [keyToCheck]: substitute },
                        ...data[index].slice(indexOfObjectWithEmptyKeyToCheck + 1)
                    ]
                )),
                ...data.slice(index + 1)
            ],
            index,
            keyToCheck,
            substitutes
        )
    }
}


const SUBSTITUTES = ["one", "two", "three"];

const result = substitute(
    [
        [
            { prop1: "abc", prop2: "" },
            { prop1: "def", prop2: "one" },
            { prop1: "ghi", prop2: "" }
        ]
    ],
    0, 
    "prop2", 
    SUBSTITUTES
)
console.log(result)
console.log("Size of result: " + result.length)

基本上，我们遍历数组，只有在当前数组没有对象且要检查的键是空字符串时才递增索引，否则我们会根据需要进行替换并在同一索引上递归。基本情况是当要检查的键不是空字符串并且索引是输入数组的最后一个索引时。

我把 Typescript 部分留给你作为练习，因为我不认为键入输入数据是这里的大问题。

如何正确实现此 JavaScript (TypeScript) 树递归函数？

How do I properly implment this JavaScript (TypeScript) Tree Recursion function?

javascript

recursion

typescript