특정 레벨에서 데이터를 포함하는 노드 수를 계산합니다. - nTree

Question

저는 nTree (n-dimensions)를 가지고 있으며 특정 깊이의 데이터 포인트를 포함하는 노드의 수를 계산하려고합니다.

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)보다 적게 이것을하는 더 좋은 방법이 있다고 확신한다.