глубина дерева python

Question

Я новичок в программировании и пытаюсь вычислить глубину дерева python. Я считаю, что моя ошибка заключается в том, что глубина - это метод класса Node, а не регулярная функция. Я пытаюсь изучить oop и надеялся использовать метод. Это может быть новая ошибка пчелиный ... Вот мой код:

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 

должен быть

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

Более читаемый версия:

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 

Этот вопрос что нет функции depth. Это метод объекта Node, поэтому вам нужно будет вызвать его из самого объекта (слева и справа). Я укоротил код до self.left.depth() if self.left else 0 и self.right.depth() if self.right else 0, чтобы удалить ранее сделанные вами проверки (они теперь неявны), поскольку я считаю, что вполне возможно, что слева находится None, а справа - Node или наоборот, что приведет к исходный код для броска AttributeError, так как None не имеет способа depth.

Редактировать

В ответ на вопрос о <something> if <some condition> else <otherwise> блока:

линия дает <something> если <some condition> истинно-у (трактуется как верно), и <otherwise> если <some condition> ложно-у (обработано как ложное)

Answer 2

Для ясности я бы предложил написать ваш метод depth следующим образом:

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

ошибка исходит от этой линии:

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

Вы используете глубину как функцию и пытаетесь применить его к левым и правым узлам. Поскольку левый и правый узлы также являются узлами, они имеют метод глубины.

Вы должны вызвать метод глубины, как это:

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

Параметр самости неявно передаются методе глубины, но при использовании его с помощью оператора точки говорит Python, что этот метод принадлежит к экземпляру Node, и это не какая-то другая функция, не связанная с объектом.

Answer 4

У вас есть четыре случая, чтобы рассмотреть:

1. Оба поддеревья пусты.
2. Левое поддеревье пусто.
3. Право только поддерева пусто.
4. Ни поддерева пуста.

Вы рассмотрели случаи 1 и 4, но пропустили 2 и 3. Исправление:

# 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