Определить количество листовых узлов в дереве против неконечных узлов - PullRequest
Новая
       16

Определить количество листовых узлов в дереве против неконечных узлов

3 голосов
/ 26 февраля 2020

У меня есть словарь, который содержит поддиректории. Это дерево решений с узлами, некоторыми листовыми узлами и некоторыми неконечными узлами. Как я могу посчитать каждый из них, учитывая словарь?

Например: 

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

Это создает дерево, как показано ниже:

enter image description here

В нем три неконечных узла и пять листовых. У меня есть общее представление о том, как я могу это сделать: 

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

Но я не уверен, как организовать рекурсивный вызов. Есть ли встроенный метод?

Ответы [ 3 ]

3 голосов
/ 26 февраля 2020

Вы можете сделать просто 

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

Однако в вашем примере есть пять «не-словарей» и пять «словарей».

1 голос
/ 26 февраля 2020

Можно создать работающий словарь, в котором хранятся значения: 

def get_count(d, c):
  for a, b in d.items():
    c[isinstance(b, dict)] += 1
    if isinstance(b, dict):
       get_count(b, c)


d = {'Outlook': {'Overcast': 'Yes', 'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny': {'Humidity': {'High': 'No', 'Normal': 'Yes'}}}}
c = {0:0, 1:0}
get_count(d, c)
print(c)

Вывод: 

{0: 5, 1: 5}
#0: elements, #1: sub-dictionaries
1 голос
/ 26 февраля 2020

Это то, что вы ищете: 

def get_count(d, c = {0:0, 1:0}):
    c[0]+=1    #count non-leaf nodes
    nodes = d.keys()
    for node in nodes:
      subnodes = d[node].values()
      for subnode in subnodes:
          if isinstance(subnode, dict)           
              get_count(subnode,c)
          else:
              c[1]+=1  #count leaf nodes

    return c




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

print(get_count(d))

Вывод: 3,5

3: нет листовых узлов

5: нет. листовых узлов

...