python - 从任意节点开始计算树中的内部(非叶)节点

Question

这是我有一棵树。我想计算从树中的任何节点开始有多少个内部节点(非叶节点)。

我现在的函数只能计算 A 以下的所有内容，即 10。但我只想要终端节点之前的那些。

• 例如。对于A，它应该是4(B，C，E，H)
• 例如。对于E，它应该是1(H)

我如何修改我的函数来做到这一点？请注意，我的数据非常大，因此递归函数会导致堆栈溢出。

  name employee
0   A   B
1   A   C
2   B   D
3   C   E
4   C   F
5   E   H
6   E   I
7   H   T
8   H   U
9   H   V

#collapse to dictionary
dict_a = {k: g["employee"].tolist() for k,g in em.groupby("name")}
dict_a

{'A': ['B', 'C'],
 'B': ['D'],
 'C': ['E', 'F'],
 'E': ['H', 'I'],
 'H': ['T', 'U', 'V']}
    
# recursive function to count lengths:
def total(k,connections):
    if k not in connections:
        return 0
    
    # number of direct connections plus their connections:
    return len(connections[k]) + sum(total(child_k, connections) for child_k in connections[k])

Answer 1

获取内部节点意味着运行遍历并且仅生成具有至少一个子节点的节点。

调用者可以灵活地将生成器转换为列表并根据需要获取长度，或者简单地进行迭代，因为该函数是通用的(特定于计数的函数似乎不必要地狭窄，但如果您需要它，它是一个简单的包装器在下面的函数上)。

def interior_nodes_from(tree, node):
    if node in tree:
        for child in tree[node]:
            if child in tree:
                yield child
                yield from interior_nodes_from(tree, child)

if __name__ == '__main__':
    tree = {'A': ['B', 'C'],
            'B': ['D'],
            'C': ['E', 'F'],
            'E': ['H', 'I'],
            'H': ['T', 'U', 'V']}
    
    for target in 'ABCDEFGH':
        interior_nodes = list(interior_nodes_from(tree, target))
        print(f'{target} => {len(interior_nodes)} children, {interior_nodes}')

输出:

A => 4 children, ['B', 'C', 'E', 'H']
B => 0 children, []
C => 2 children, ['E', 'H']
D => 0 children, []
E => 1 children, ['H']
F => 0 children, []
G => 0 children, []
H => 0 children, []

如果您的树深度超过了调用堆栈大小，您可以使用显式堆栈而不是递归:

def interior_nodes_from(tree, node):
    if node in tree:
        stack = [node]
        
        while stack:
            for child in tree[stack.pop()]:
                if child in tree:
                    yield child
                    stack.append(child)