时间戳

首页 > 解决方案 > 如何按属性减少树节点？

javascript - 如何按属性减少树节点？

问题描述

我试图减少树，其中visible = true or undefined：

演示链接

function reduce(node: any): any {
    if(!node || !node?.children) return;
    node.children = node.children.filter((child: any) => child?.visible === undefined || child.visible === true);

    for(let i =0 ;i<=node.children.length; i++) {
        reduce(node.children[i]);
    }

    return node;

}

console.log(reduce(data));

所以，我filter每个孩子的元素数组，但我无法得到如何返回这个修改后的数组？

在里面node.children我得到了映射的元素，然后我需要更深入地浏览每个元素。

标签： javascripttypescript

解决方案

我同意第一次尝试做对并不容易，我必须说你几乎做对了。事实证明，有很多方法可以解决您的问题，但就个人而言，我喜欢基于归纳构造算法的逻辑，以使步骤更清晰。

目标

在这里你可以确定你想要什么。根据我从您那里得到的信息，需要遍历结构树的每个节点并过滤具有可见属性等于的节点true。

{
  id: number, 
  name: string, 
  visible: boolean, 
  children?: node[]
}

对孩子数量的强感应

  1. 基本情况：
    a）当输入是假的时，这里的完整列表返回一棵空树。
    b）当它没有children属性时，检查它是否可见，如果它返回树。

  2. 归纳假设：假设你知道如何解决任何有k孩子的树的问题（k 整数，0 <= k < n）。

  3. 一般情况：证明您可以求解具有n孩子（n 个整数）的树。

解决方案的想法

输入：n 个孩子的树

  1. 使用基本情况if 检查描述来创建第一行。
  2. 遍历树的每个孩子并检查它是否具有visible设置为的属性true。
  3. 对它们应用归纳假设（因为它们的节点少于 n 个）。
  4. 将每个部分解决方案推送到新数组（一般情况）。
  5. 替换先前获得的子元素的原始数组。

伪代码

algorithm reduce
   input: tree with n children
   output: same tree filtered under conditions

 if input is not a tree then 
    return an empty tree
 else if input has no children attribute and its visible attribute is true then
    return the input tree
 else 
    filteredChildren := new empty Array
    for each node in tree do
       if node visible attribute is true then
           ans := reduce(node)   -- Induction Hypothesis
           filteredChildren.append(ans)
    tree.children = filteredChildren
    return tree

打字稿算法

如此处所见，请使用您的输入进行检查。

function reduce(tree: any): any {
    if (!tree) return {};
    if (!tree.children) return tree.visible === true ? tree : {};
    tree.children = tree.children.filter((child: any) => child.visible === true)
                                 .map((child: any) => reduce(child))
    return tree;
}

推荐阅读