python - 确定树中叶节点数与非叶节点数

Question

我有一本包含子词典的词典。它是一个带有节点的决策树，一些叶节点和一些非叶节点。在给定字典的情况下，我如何计算其中的每一个？

例如:

{'Outlook': {'Overcast': 'Yes', 'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny': {'Humidity': {'High': 'No', 'Normal': 'Yes'}}}}

这会生成一棵如下所示的树:

其中有3个非叶节点和5个叶节点。我对如何做到这一点有一个大致的了解:

def count(d):
  a, b = 0, 0 # non-leaf nodes and leaf nodes
  for key, value in d.items():
    if isinstance(value, dict):
      a += 1
      # some recursive call on value
    else:
      b+= 1
  return a, b

但我不确定如何组织递归调用。有内置方法吗？

Answer 1

你可以简单地做

def count(d):
  a, b = 0, 0 # subdicts and not-subdicts
  for key, value in d.items():
    if isinstance(value, dict):
      a += 1
      suba, subb = count(value)
      a += suba
      b += subb
    else:
      b += 1
  return a, b

但是，您的示例有五个“非字典”和五个“字典”。