Altezza dell'albero binario

Question

Sto cercando di implementare un metodo ricorsivo per calcolare l'altezza di un albero binario. Ecco il -Codice "altezza":

def height(self): 
    if self.root==None: 
     return 0 
    return max(height(self.root.left), height(self.root.right))+1 

Quando provo a chiamare la funzione, ottengo il seguente msg di errore:

NameError: name 'height' is not defined 

Qualcuno vede il problema?

Answer 1

Questo è un metodo della classe, quindi è necessario chiamarlo da un'istanza (self) o dalla classe stessa. Anche se non funzionerà come credi, a meno che non lo definisci come staticmethod o cambi la tua chiamata, ad es.

def height(self): 
    return 1 + max(self.left.height() if self.left is not None else 0, 
        self.right.height() if self.right is not None else 0) 

o

@staticmethod 
def height(self): 
    return 1 + max(self.height(self.left) if self.left is not None else 0, 
        self.height(self.right) if self.right is not None else 0) 

Si noti, che non si dovrebbe usare == da confrontare con None (complimenti a timgeb). E devi verificare se esistono anche i nodi figli. E il tuo algoritmo non funziona, quindi l'ho modificato leggermente.

Esempio:

class Node: 
    def __init__(self, root=None, left=None, right=None): 
     self.root = root 
     self.left = left 
     self.right = right 

    def height(self): 
     return 1 + max(self.left.height() if self.left is not None else 0, 
         self.right.height() if self.right is not None else 0) 


# Create a binary tree of height 4 using the binary-heap property 
tree = [Node() for _ in range(10)] 
root = tree[0] 

for i in range(len(tree)): 
    l_child_idx, r_child_idx = (i + 1) * 2 - 1, (i + 1) * 2 
    root_idx = (i + 1) // 2 
    if root_idx: 
     tree[i].root = tree[root_idx] 
    if l_child_idx < len(tree): 
     tree[i].left = tree[l_child_idx] 
    if r_child_idx < len(tree): 
     tree[i].right = tree[r_child_idx] 

print(root.height()) # -> 4 

Answer 2

io non sono sicuro di come si definisce il vostro albero binario. Ma su un nodo ad albero di solito hai solo una radice e più figli. Ho la sensazione che questo metodo porti ad un loop infinito. self.root.left e self.root.right sono esattamente io e mio fratello ...

Qui probabilmente devi chiamare il metodo dalle istanze self.root.left e self.root.right senza argomenti aggiuntivi :

def height(self): 
    if self.root==None: 
     return 0 
    return max(self.root.left.height(), self.root.right.height())+1