python - 在Python中计算普通树中的节点

Question

我创建了一个不是二叉树的树结构，并且很难获得正确的节点数。

class TreeNode(object):
  def __init__(self, name='root', children=None,Parent=[]):
    self.Name = name
    self.Parents=Parent

    self.Children = []
    if children is not None:
        for child in children:
            self.add_child(child.Name)

 def __repr__(self):
   return self.Name

 def add_child(self, node):    
  self.Children.append(node)

这是我为了计算树中节点数量而尝试做的最新事情。

def countNodes(Tree):      

   for Child in Tree.Children:
      return countNodes(Child)+1

   return 1

有人可以解释一下为什么这不起作用吗？编辑:我应该澄清一下，当我说不起作用时，它给了我图表中节点数量的完全错误的计数。

Answer 1

你的countNodes功能不太好。父节点可以有两个子节点，如果您在 for 循环中放置 return 语句，它将返回第一个子节点计数，而第二个子节点计数将丢失。你需要做这样的事情:

def countNodes(Tree):      
   count = 1
   for Child in Tree.Children:
      count +=  countNodes(Child)
   return count