如何递归计算树的宽度

Question

我有一个数据结构为的树

root: {
children:[
{children: [
{children:[]}
]},
{children: []}
]
}

这是一个树的例子，结果应该是4(最大宽度(

R
/  |  
A   B  X
/  / 
C  D E  F

G   

Answer 1

要使用递归实现这一点，您可以制作一个助手函数，以序列的形式返回当前级别的大小，然后返回每个级别的子级大小之和。从序列中取最大尺寸进行输出：

from itertools import zip_longest
def max_tree_width(tree):
def widths(tree):
return len(tree), *map(sum, zip_longest(*map(widths, tree.values()), fillvalue=0))
return max(widths(tree))

因此，给定以下输入，改编自您问题中的样本树：

tree = {
'R': {
'A': {
'C': {},
'D': {
'G': {}
}
},
'B': {
'E': {},
'F': {}
},
'X': {}
}
}

max_tree_width(tree)将返回：4

演示：https://replit.com/@blhsing/粗心的PutridAutocad

Answer 2

这当然可以通过多种方式解决。但这里有一个使用尾部递归的变体：

def width_calc(trees, maxwidth=0):                                             
# trees should be a list of all subtrees at the current level, so if its a 
# dict (as expected in the first call) it is wrapped in a list.            
if type(trees) is dict:                                                    
trees = [trees]                                                        
# Get all subtrees at the current level                                    
subtrees = [v for tree in trees for v in tree.values()]                    
# If there is subtrees at the current level then recurse down one more     
# level. Also calculate the maxwidth so far and send to the next level.    
if subtrees:                                                               
return width_calc(subtrees, max(maxwidth, len(subtrees)))              
# There is no subtrees at this level so we reached the last leaves and the 
# maxwith can be returned.                                                 
return maxwidth                     

使用您的树数据(由另一个anser中的@blhsing实现(，调用width_calc(tree)将返回4。