V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
NewConn
V2EX  ›  程序员

求助:关于树的构建,还要加上分类

  •  
  •   NewConn · 2022-09-16 10:38:11 +08:00 · 1327 次点击
    这是一个创建于 826 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有一个需求,小弟算法能力不强,不知道怎么实现
    有一批平铺的数据,每个数据有 parentId ,Id ,type 等属性;按 node.parentId=parentNode.id 构建完之后是一棵树,然后统一挂在一个虚拟的根节点,也即真实数据是一级节点的 array
    以上步骤都没有问题,难点在下面:
    按数据的 type 进行分类,每个分类建立一个虚拟的树节点,统一挂在一个虚拟的根节点下;
    type 的虚拟节点下的真实数据,也需要按父子关系把树构建出来,并且当前节点在树上到根节点也连带出来(向上时,如果节点数据不属于此 type ,也需要展示,此时加一个 readonly 标记)

    我思考了如下方案:
    ( 1 )先把平铺的数据分类,每个分类下的 array 的每个元素进行构建树,但是如果两个节点(有如下可能:深度一样 /不一样;有 /没有父子关系)都在树的某个分支下,可能会构建出 2 棵树,且不好判断
    ( 2 )先构建树,然后提取符合特征的节点


    这个问题把小弟难住了啊,不管怎么处理好像都不对
    8 条回复    2022-09-19 19:06:59 +08:00
    sillydaddy
        1
    sillydaddy  
       2022-09-16 11:16:36 +08:00
    真佩服我竟然读懂了。

    用你说的第 2 种方案比较方便吧?从完整的树🌲里面,提取出每个 type 对应的子树:

    ```
    function clipNode(node, type){
    if(node.type != type && node.parent.type == type){
    node.parent = null; //从 parent 中裁剪掉这个 node
    }else{
    clipNode(node.parent);//向 parent 递归
    }
    }

    var leaf_nodes = node_has_no_children(all_nodes);
    leaf_nodes.forEach((node)=>clipNode(node, "sometype"));

    var new_leaf_nodes = node_has_no_children(all_nodes); //新的叶子节点,因为一些分支被裁剪掉了
    var result = nodes_that_can_reach_root(new_leaf_nodes);
    ```


    对所有的「叶子」节点向上递归,child->parent ,如果父节点属于 type ,而子节点不属于 type ,把子节点裁剪掉,中止这个路径的递归。

    最后收集那些没有被裁剪掉的分支,即可以通过.parent.parent.parent...一直连接到虚拟 root 节点的叶子节点。这些叶子节点都属于没有被裁剪掉的分支。用这些叶子节点构造树🌲就是 type 对应的树。
    jjwjiang
        2
    jjwjiang  
       2022-09-16 11:20:58 +08:00
    type 的虚拟节点下的真实数据,也需要按父子关系把树构建出来,并且当前节点在树上到根节点也连带出来(向上时,如果节点数据不属于此 type ,也需要展示,此时加一个 readonly 标记)

    ==> 没太明白,如果节点 type 不属于这个 type 也要展示而不是裁剪,那岂不是 type 的树就和原始树一样吗?
    NewConn
        3
    NewConn  
    OP
       2022-09-16 11:30:41 +08:00
    @jjwjiang 只是向上递归到根节点,向下递归的子孙节点,如果没有这个 type 的就不展示
    NewConn
        4
    NewConn  
    OP
       2022-09-16 11:31:20 +08:00
    @sillydaddy 谢谢,我研究下
    rrfeng
        5
    rrfeng  
       2022-09-16 11:58:04 +08:00 via Android
    不如说原始需求。
    NewConn
        6
    NewConn  
    OP
       2022-09-19 16:30:21 +08:00
    @sillydaddy 老哥,功能可以解决,就是性能非常慢。
    主要我的树的节点,只有父里面有一个 List<Node>存储子的对象的列表。这样的话,子就只能存父的 id ,而不能存对象,否则就会出现循环引用。所以每次裁剪的时候,都要在树上从上往下遍历。总体来看,需要 type 和 leaf_nodes 的 2 层循环,里面每次还需要从上往下遍历一次树(这个又是每级子节点的循环+每层的递归)。原始数据不多,却需要 30s
    NewConn
        7
    NewConn  
    OP
       2022-09-19 16:32:49 +08:00
    @jjwjiang 按 1 楼老哥思路,我又梳理了一下。其实只裁剪一种情况:在树上从上向下,裁剪掉某个子树,这颗子树的所有节点都不属于 type 。
    sillydaddy
        8
    sillydaddy  
       2022-09-19 19:06:59 +08:00
    @NewConn , #7
    是这样的,所以我贴在 1#楼的代码有问题啊。

    不过 30s 有点难以想象,你的代码有几层循环啊?

    根据你说的「原始数据不多」,可以考虑用空间换时间,比如要判断「子树的所有节点都不属于 type 」,可以为每个节点都保存一个用于判断「是否包含某个 type 」的数组:
    type Node = {
    ...
    children: Node[];
    hasChildOfType : boolean[COUNT_OF_TYPES]; //NUM_OF_TYPES 是所有 type 的数量
    };

    然后给所有级别的父节点添加对应的标记:
    all_nodes.forEach( node => {
    node.hasChildOfType[node.type]=true;
    node.parent.hasChildOfType[node.type]=true;
    node.parent.parent.hasChildOfType[node.type]=true;
    ...
    });

    这样裁剪的时候再判断就省时间了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3184 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:41 · PVG 18:41 · LAX 02:41 · JFK 05:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.