沒有定義樹結構的遞歸樹總和

-1

我有一個節點和子節點的字典（1）Dictionary<int,int[]>和與每個節點相關的權重列表（2）。字典可以解釋如下：例如：鍵1的值爲3,4，這意味着節點id = 1是節點3和節點4的父節點。鍵3的值爲5,6,8，這意味着節點id = 3是父節點到節點5,6和8等等。第二個列表只是一個權重列表，其中索引代表權重與節點ID相關聯。沒有定義樹結構的遞歸樹總和

我想爲列表（1）的每個關鍵節點計算其所有子節點權重的總和。

我認爲這個問題類似於遞歸樹總和，雖然我的列表沒有設置爲樹結構。

我該如何繼續？

來源

2017-05-03 Samuel Letellier-Duchesne

歡迎StackOverflow上。請閱讀並遵守幫助文檔中的發佈準則。 [在主題]（http://stackoverflow.com/help/on-topic）和[如何提問]（http://stackoverflow.com/help/how-to-ask）適用於此處。 StackOverflow不是一個設計，編碼，研究或教程服務。 – Prune

您應該如何繼續？選擇一種編程語言並編寫代碼總結，如果適合你或者只是用手做:)。是的，如果您選擇編寫代碼來計算總和的路徑，這種問題非常適合遞歸機制。 – Claudio

@Prune，我會試着在未來制定更好的問題。謝謝 –

這裏一個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]

來源

2017-05-03 23:45:42 Claudio

在工作中的同事想出了這個優雅的解決方案（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();

來源

2017-05-05 00:59:45

沒有定義樹結構的遞歸樹總和

回答

相關問題