Zählen der Anzahl der Knoten, die Daten auf einer bestimmten Ebene enthalten - nTree

Question

Ich habe einen nTree (n-Dimensionen) und ich möchte die Anzahl der Knoten mit Datenpunkten in einer bestimmten Tiefe berechnen. Hier ist die Baumstruktur und die Funktion, die ich zu verwenden Ich versuche:

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 

Ich bin mir bewusst, dass meine Methode ein wenig ineffizient ist, aber ich will es zunächst arbeiten, dann kann ich es optimieren. Ich habe einen anderen Beitrag zu diesem Thema gelesen und meine Methode ist sehr ähnlich zu der der anderen Beiträge, aber es funktioniert nicht für einen nTree. In meinem Fall habe ich 64 Kinder/Elternteil. Außerdem bin ich mir nicht sicher, ob die PreOrder-, PostOrder-, InOrder- oder BreadthFirst-Traversale funktionieren, da ich nicht auf ein linkes oder rechtes Unterkind verweisen kann. Irgendwelche Vorschläge zur Verbesserung/zum Funktionieren der Methode?

Answer 1

Problem behoben. Für alle, die eine Lösung hier auf der Suche ist die Methode:

#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) 

Dieses Verfahren verwendet ein Tiefes Traversal-Modell, so dass es jeden Knoten im Baum überprüft. Ich bin sicher, es gibt bessere Möglichkeiten, dies in weniger als O (n) zu tun.