głębokość pytona drzewa

Question

Jestem nowy w programowaniu i próbuję obliczyć głębokość drzewa Pythona. Uważam, że mój błąd jest taki, ponieważ głębokość jest metodą klasy węzła, a nie zwykłą funkcją. Próbuję się nauczyć oop i miałem nadzieję, że użyję metody. To może być nowy błąd pszczoła ... Oto mój kod:

class Node: 

    def __init__(self, item, left=None, right=None): 
     """(Node, object, Node, Node) -> NoneType 
     Initialize this node to store item and have children left and right. 
     """ 
     self.item = item 
     self.left = left 
     self.right = right 

    def depth(self): 
     if self.left == None and self.right == None: 
      return 1 

     return max(depth(self.left), depth(self.right)) + 1 

i receive this error: 

>>>b = Node(100) 

>>>b.depth() 

1 

>>>a = Node(1, Node(2), Node(3)) 

>>>a.depth() 

Traceback (most recent call last): 
    File "C:\Program Files\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 1, in <module> 
    # Used internally for debug sandbox under external interpreter 
    File "C:\Program Files\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line 15, in depth 
builtins.NameError: global name 'depth' is not defined 

Answer 1

def depth(self): 
    if self.left == None and self.right == None: 
     return 1 

    return max(depth(self.left), depth(self.right)) + 1 

powinny być

def depth(self): 
    return max(self.left.depth() if self.left else 0, self.right.depth() if self.right else 0) + 1 

bardziej czytelna wersja:

def depth(self): 
    left_depth = self.left.depth() if self.left else 0 
    right_depth = self.right.depth() if self.right else 0 
    return max(left_depth, right_depth) + 1 

Problem jest że nie ma funkcji depth. Jest to metoda obiektu Node, więc musisz wywołać ją z samego obiektu (w lewo i w prawo). Skróciłem kod do self.left.depth() if self.left else 0 i self.right.depth() if self.right else 0, aby usunąć sprawdzenia, które poprzednio masz (są one teraz ukryte), ponieważ uważam, że jest całkowicie możliwe, że lewe jest None, podczas gdy prawo to jest Node lub odwrotnie, co spowodowałoby Oryginalny kod do przesłania AttributeError od None nie ma metody depth.

Edycja

W odpowiedzi na pytanie o bloku <something> if <some condition> else <otherwise>:

Linia daje <something> jeśli <some condition> prawda Y (traktowane jako prawdziwy) i <otherwise> jeśli <some condition> jest fałszywie-r (traktowane jako fałszywe)

Answer 2

Dla przejrzystości chciałbym zaproponować napisanie swojej metody depth w ten sposób:

def depth(self): 
    current_depth = 0 

    if self.left: 
     current_depth = max(current_depth, self.left.depth()) 

    if self.right: 
     current_depth = max(current_depth, self.right.depth()) 

    return current_depth + 1 

Answer 3

Błąd pochodzi z tej linii:

return max(depth(self.left), depth(self.right)) + 1 

Używasz głębokość w funkcji i stara się stosować go do lewego i prawego węzłów. Ponieważ lewy i prawy węzeł są również węzłami, mają one metodę głębi.

Powinieneś być wywołanie metody głębokości takiego:

return max(self.left.depth(), self.right.depth()) + 1 

Parametr samo jest domyślnie przekazywane do metody głębokości, ale używając go z operatorem dot mówi Python, że ta metoda należy do węzła instancji i to nie jest jakaś inna funkcja niezwiązana z obiektem.

Answer 4

Masz cztery przypadki do rozważenia:

1. Oba poddrzewa są puste.
2. Sam lewy poddrzewo jest pusty.
3. Samo prawe poddrzewo jest puste.
4. Żadne pod poddrzewo nie jest puste.

Zajęliście przypadki 1 i 4, ale brakowało 2 i 3. Poprawka:

# Return height of tree rooted at this node. 
def depth(self): 
    if self.left == None and self.right == None: 
     return 1 
    elif self.left == None: 
     return self.right.depth() + 1 
    elif self.right == None: 
     return self.left.depth() + 1 
    else: 
     return max(self.left.depth(), self.right.depth()) + 1