首页 文章

递归树和不定义树结构

提问于
浏览 1986
-1

我有一个节点和子节点的字典(1) Dictionary<int,int[]> 和一个与每个节点相关的权重列表(2) . 字典可以解释如下:例如:键1具有值3,4,这意味着节点id = 1是节点3和4的父节点 . 键3具有值5,6,8,这意味着节点id = 3是父节点5,6和8 ...等等 . 第二列表只是权重列表,其中索引表示权重与之相关联的节点ID .

我想计算列表(1)的每个关键节点,它是所有子节点权重的总和 .

我认为这个问题类似于递归树和,尽管我的列表没有设置为树结构 .

我该怎么办?

2 回答

  • 0

    这是一个Python版本的解决方案,可以实现您想要实现的目标:

    dctNodeIDs_vs_Childs = {}
    dctNodeIDs_vs_Childs[1] = (2,3,4)
    dctNodeIDs_vs_Childs[2] = (13,14,15)
    dctNodeIDs_vs_Childs[3] = (5,6,7,8)
    dctNodeIDs_vs_Childs[4] = (9,10,11,12)
    lstNodeIDs_vs_Weight = [None,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
    
    def getSumOfWeights(currNodeID, lstNodeIDs_vs_Weight = lstNodeIDs_vs_Weight, dctNodeIDs_vs_Childs = dctNodeIDs_vs_Childs):
        sumOfWeights = 0
        print("#currNodeID", currNodeID)
        if currNodeID not in dctNodeIDs_vs_Childs:
            sumOfWeights += lstNodeIDs_vs_Weight[currNodeID]
        else: 
            for childNodeID in dctNodeIDs_vs_Childs[currNodeID]:
                print("## childNodeID", childNodeID)
                if childNodeID not in dctNodeIDs_vs_Childs:
                    sumOfWeights += lstNodeIDs_vs_Weight[childNodeID]
                else:
                    sumOfWeights += lstNodeIDs_vs_Weight[childNodeID] + sum( [ getSumOfWeights(nodeID) for nodeID in dctNodeIDs_vs_Childs[childNodeID] ] )
        return sumOfWeights
    
    lstNodeIDs_vs_WeightsOfChildNodes = [None for _ in range(len(lstNodeIDs_vs_Weight)+1)]       
    for nodeID in dctNodeIDs_vs_Childs.keys():
        print("nodeID =", nodeID)
        lstNodeIDs_vs_WeightsOfChildNodes[nodeID] = getSumOfWeights(nodeID)
    print("---")
    print(lstNodeIDs_vs_WeightsOfChildNodes)
    

    给出以下输出:

    nodeID = 1
    #currNodeID 1
    ## childNodeID 2
    #currNodeID 13
    #currNodeID 14
    #currNodeID 15
    ## childNodeID 3
    #currNodeID 5
    #currNodeID 6
    #currNodeID 7
    #currNodeID 8
    ## childNodeID 4
    #currNodeID 9
    #currNodeID 10
    #currNodeID 11
    #currNodeID 12
    nodeID = 2
    #currNodeID 2
    ## childNodeID 13
    ## childNodeID 14
    ## childNodeID 15
    nodeID = 3
    #currNodeID 3
    ## childNodeID 5
    ## childNodeID 6
    ## childNodeID 7
    ## childNodeID 8
    nodeID = 4
    #currNodeID 4
    ## childNodeID 9
    ## childNodeID 10
    ## childNodeID 11
    ## childNodeID 12
    ---
    [None, 119, 42, 26, 42, None, None, None, None, None, None, None, None, None, None, None, None]
    
  • 0

    一位在工作的同事提出了这个优雅的解决方案(需要2个词典) . 虽然可能不是最有效的 .

    double MethodName(int Id) => FirstDic.ContainsKey(Id) ? FirstDic[Id].Sum(n => MethodName(n)) : SecondDic.Where(y => y.Key == Id).Select(x => x.Value).Sum();

相关问题