统计包含特定级别数据的节点数-- nTree

Question

我有一个维度(n维)，我想要计算在特定深度包含数据点的节点的数量。下面是我尝试使用的树结构和函数：

class nTree:

    def initialize(self, hypercube_coordinates, depth=0):
        self.data = [] #holds the data - this tells if the node is empty or not
        self.children = [] 
        self.depth = depth
        self.hypercube = hypercube #coordinates 

    #a bit inefficient since we are theoretically visiting each node
    #can be optimized later
    def count_nodes_at_level(self, depth):
        count = 0
        for child in self.children:
            if child.depth == depth:
                count += child.count_nodes_at_level(self.depth)
            else:
                child.count_nodes_at_level(depth)
        return count

我知道我的方法有点低效，但我希望它能先工作，然后再优化它。我读过一个关于这个问题的不同的帖子，我的方法和其他帖子的方法非常相似，但它不适用于nTree。在我的例子中，我有64个孩子/父母。此外，我不确定是否可以使用PreOrder、PostOrder、InOrder或BreadthFirst遍历，因为我不能引用左或右子对象。对于改进/使该方法有效，有什么建议？

Answer 1

问题已修复。对于任何正在寻找解决方案的人来说，这里是一个方法：

#countNodesAtLevel - returns the number of non-empty nodes at a given level
#Parameters:
#    depth - depth at which we are counting

def _countNodesAtLevel(self, depth, count=0):

    #root level = 0, return only 1 for the data
    if depth == 0 and self.data:
        return 1
    else:
        for child in self.children:
            if child.depth == depth and child.data:
                count+=1
                count+=child.countNodesAtLevel(depth)
            else:
                count+=child.countNodesAtLevel(depth)
    return count

#USER FUNCTION
#countNodesAtLevel - returns the number of non-empty nodes at a given level
def countNodesAtLevel(self, depth):
    count = self._countNodesAtLevel(depth)
    print(count) 

此方法使用深度优先遍历模型，因此它检查树中的每个节点。我相信有更好的方法可以在少于O(n)的时间内做到这一点。