javascript - 递归查找 child 的 child 并删除

Question

我有一个包含子级的数组，所有内容都通过parentId 相关。

示例:

[
{id: 1, parentid:0},{id: 2, parentid:1},
{id: 3, parentid:2},{id: 4, parentid:2},{id: 10, parentid:4},
{id: 5, parentid:0},{id: 6, parentid:5},{id: 7, parentid:7}
]

我想删除 Id:1 的对象及其所有相关子对象。这就是这些对象

{id: 1, parentid:0},{id: 2, parentid:1},
{id: 3, parentid:2},{id: 4, parentid:2},{id: 10, parentid:4}

Answer 1

这是一种使用递归来完成此操作的实用方法。编号的项目符号点与下面代码中编号的注释相匹配。

1. (base) 没有节点，因此没有什么需要处理的；返回结果r
2. (归纳)至少有一个节点。如果节点的id或parentid在集合s中，则已找到匹配的节点。将节点的 id 添加到集合中，并使用部分结果 r 和剩余节点 more 开始搜索。
3. (归纳)至少有一个节点，它与我们正在搜索的 id 不匹配。将节点追加到结果中并继续搜索更多个节点。

const removeFamily =
  ( id = 0
  , [ node, ...more ] = []
  , s = new Set ([ id ])
  , r = []
  ) =>
    node === undefined
      ? r                               // 1
      : s .has (node.id) || s .has (node.parentid)
          ? removeFamily                // 2
              ( id
              , [ ...r, ...more ]
              , s .add (node.id)
              , []
              )
          : removeFamily                // 3
              ( id
              , more
              , s
              , [ ...r, node ]
              )

const nodes =
  [ { id: 1, parentid: 0 }
  , { id: 2, parentid: 1 }
  , { id: 3, parentid: 2 }
  , { id: 4, parentid: 2 }
  , { id: 10, parentid: 4 }
  , { id: 5, parentid: 0 }
  , { id: 6, parentid: 5 }
  , { id: 7, parentid: 7 }
  ]

const newNodes =
  removeFamily (1, nodes)

console .log (newNodes)
// [ { id: 5, parentid: 0 }
// , { id: 6, parentid: 5 }
// , { id: 7, parentid: 7 }
// ]

这里用 if 语句重写，如果这可以帮助您更好地理解它 -

const removeFamily =
  ( id = 0
  , [ node, ...more ] = []
  , s = new Set ([ id ])
  , r = []
  ) =>
  { if (node === undefined)
      return r               // 1
    else if (s .has (node.id) || s .has (node.parentid))
      return removeFamily    // 2
        ( id
        , [ ...r, ...more ]
        , s .add (node.id)
        , []
        )
    else
      return removeFamily    // 3
       ( id
       , more
       , s
       , [ ...r, node ]
       )
  }

这是一个堆栈安全的变体，它使用通用的loop/recur接口(interface)。即使节点列表可能包含数百万个节点，此版本也能正常工作。它还有一个稍微好一点的公共(public)接口(interface)，因为只有两 (2) 个参数可以在调用站点进行配置 -

const recur = (...values) =>
  ({ recur, values })

const loop = f =>
{ let a = f ()
  while (a && a.recur === recur)
    a = f (...a.values)
  return a
}

const removeFamily = (id = 0, nodes = []) =>
  loop
    ( ( [ node, ...more ] = nodes
      , s = new Set ([ id ])
      , r = [] 
      ) =>
        node === undefined
          ? r                           // 1
          : s .has (node.id) || s .has (node.parentid)
            ? recur                     // 2
                ( [ ...r, ...more ]
                , s .add (node.id)
                , []
                )
            : recur                     // 3
                ( more
                , s
                , [ ...r, node ]
                )
    )

const nodes =
  [ { id: 1, parentid: 0 }
  , { id: 2, parentid: 1 }
  , { id: 3, parentid: 2 }
  , { id: 4, parentid: 2 }
  , { id: 10, parentid: 4 }
  , { id: 5, parentid: 0 }
  , { id: 6, parentid: 5 }
  , { id: 7, parentid: 7 }
  ]


const newNodes =
  removeFamily (1, nodes)

console .log (newNodes)
// [ { id: 5, parentid: 0 }
// , { id: 6, parentid: 5 }
// , { id: 7, parentid: 7 }
// ]