计算 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 语句，它将 return 第一个子节点计数，第二个子节点计数将丢失。你需要做这样的事情：

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

Answer 2

Just to add @levi has missed an edge case where root is None

所以修改后的代码将是：

def numNodes(root):
    if root == None:
        return 0 
    node = 1
    for child in root.children:
        node = node + numNodes(child)
    return node

计算 python 中一般树中的节点

Counting nodes in General tree in python

python

tree