Javascript - 递归地从树中删除某种类型的节点，但重新附加并传播符合条件的子节点

Question

我正在 JSON 树上编写递归函数{name, type, [children]}以删除特定类型的节点。但是，如果已移除节点的子节点不是要移除的类型，则它们应该重新附加到父节点。我遇到了以下困难：假设我想删除以下树上的类型 b：const sampleData = [{name: "parent",type: "a",children: [{    name: "childA",    type: "a",    children: null    },{    name: "childB",    type: "b",    children: [{        name: "grandChildA",        type: "a",        children: null        },{        name: "grandChildB",        type: "a",        children: null        }]    },{    name: "childC",    type: "a",    children: null    }]}]parent 的原始 children 是[childA, childB, childC]. 移除后，父母应该有孩子[childA, grandChildA, grandChildB, childC]。但是，我得到的结果是[childA, [grandChildA, grandChildB], childC].我知道我需要把它分散开来，但我不确定在回避中在哪里做。这是我现在拥有的功能（我知道我在错误的地方使用了扩展语法）：const removeType = (node, type) => {    //if the node should not be removed        if (node.type !== type){        //if the node has children, recursively call to prune children        if (node.children && node.children.length > 0){            node.children = [...node.children.map(child => removeType(child, type))                                             .filter(child => child !== null)]            return node        }        //if the node has no children, return the node        else return node    }    //if the node should be removed    else if (node.type === type){        //if the node has children, recursively call, then reattach the children        if (node.children && node.children.length > 0){            node.children = [...node.children.map(child => removeType(child, type))                                             .filter(child => child !== null)]            return node.children        }        //        else return null    }}

Answer 1

更新

我想你可以为此使用 reduce，我现在没有电脑来测试它，但它会是这样的

const removeType = (node, type) => {

   if (node === null) {

     return null;

   } else {

    return node.reduce((acc, child) => {

      if(child["type"] === type) {

        const removedChild = removeType(child["children"], type);

        acc = [...acc, ...removedChild];

      } else {

        child.children = removeType(child["children"], type);

        acc.push(child);

      }

      return acc;

    }, []);

  }

}

第二次更新

代码减少：

const removeType = (node, type) => {

    if (!node) return;

    return node.reduce((acc, child) => {

        if(child["type"] === type) {

            const removedChild = removeType(child["children"], type);

            acc = [...acc, ...removedChild];

        } else {

            child.children = removeType(child["children"], type);

            acc.push(child);

        }

        return acc;

    }, []);

}

Answer 2

我认为这个答案与提供的其他答案完全不同，可以将其添加为替代方案。它具有与 Thankyou 的答案相同的递归结构，但它简化了假设，即您的输入始终是一个数组，所有非零children节点也是如此。

const removeType = (node, target) =>

  node .flatMap (({type, children, ...rest}) =>

    type === target

      ? children ? removeType (children, target) : []

      : [{...rest, type, children: children && (removeType (children, target))}]

  )

const sampleData = [{name: "parent", type: "a", children: [{name: "childA", type: "a", children: null},{name: "childB", type: "b", children: [{name: "grandChildA", type: "a", children: null},{name: "grandChildB", type: "a", children: null}]}, {name: "childC", type: "a", children: null}]}]

console .log (

 removeType (sampleData, 'b')

)

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

Answer 3

Array.prototype.flatMap这是使用、一些数学归纳法和一些相互递归来简化程序的方法-

• removeType接受一个数组nodes和一个要删除的查询类型，q

• removeType1接受单个 node和要删除的查询类型，q

const removeType = (nodes, q) =>

  (nodes || []).flatMap(n => removeType1(n, q))  // <-- removeType1

const removeType1 = (node, q) =>

  q === node.type

    ? removeType(node.children)                  // <-- removeType

    : { ...node, children: removeType(node.children, q) } // <-- removeType

const input = 

  [{name:"parent",type:"a",children:[{name:"childA",type:"a",children:null},{name:"childB",type:"b",children:[{name:"grandChildA",type:"a",children:null},{name:"grandChildB",type:"a",children:null}]},{name:"childC",type:"a",children:null}]}]

  

const result =

  removeType(input, "b")

console.log(result)

输出 -

[

  {

    "name": "parent",

    "type": "a",

    "children": [

      {

        "name": "childA",

        "type": "a",

        "children": []

      },

      {

        "name": "grandChildA",

        "type": "a",

        "children": []

      },

      {

        "name": "grandChildB",

        "type": "a",

        "children": []

      },

      {

        "name": "childC",

        "type": "a",

        "children": []

      }

    ]

  }

]

请注意，这result是一个新对象，input不会因调用.removeType

相互递归非常适合解决上述问题，但如果您真的只想要一个函数怎么办？

const removeType = (t, q) =>

  Array.isArray(t)                             // <-- array

    ? t.flatMap(node => removeType(node, q))

: Object(t) === t                              // <-- object (node)

    ? q === t.type

        ? removeType(t.children, q)

        : { ...t, children: removeType(t.children, q) }

: t                                            // <-- else (no operation)

const input = 

  [{name:"parent",type:"a",children:[{name:"childA",type:"a",children:null},{name:"childB",type:"b",children:[{name:"grandChildA",type:"a",children:null},{name:"grandChildB",type:"a",children:null}]},{name:"childC",type:"a",children:null}]}]

  

const result =

  removeType(input, "b")

console.log(result)

输出大部分是相同的，除了注意这个是如何保存的children: null。我们的原始程序产生更正确的children: []-

[

  {

    "name": "parent",

    "type": "a",

    "children": [

      {

        "name": "childA",

        "type": "a",

        "children": null

      },

      {

        "name": "grandChildA",

        "type": "a",

        "children": null

      },

      {

        "name": "grandChildB",

        "type": "a",

        "children": null

      },

      {

        "name": "childC",

        "type": "a",

        "children": null

      }

    ]

  }

]