độ sâu của một cây trăn cây

Question

tôi mới lập trình và đang cố gắng tính toán độ sâu của cây trăn. Tôi tin rằng lỗi của tôi là bởi vì chiều sâu là một phương thức của lớp Node và không phải là một hàm bình thường. Tôi đang cố gắng tìm hiểu oop và hy vọng sẽ sử dụng một phương pháp. Đây có thể là một lỗi ong mới ... Đây là mã của tôi:

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 

nên

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

Một phiên bản dễ đọc hơn:

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 

Vấn đề là rằng không có chức năng depth. Đó là một phương thức của đối tượng Node, vì vậy bạn sẽ cần phải gọi nó từ chính đối tượng đó (trái và phải). Tôi rút ngắn mã thành self.left.depth() if self.left else 0 và self.right.depth() if self.right else 0 để xóa các kiểm tra bạn đã có trước đây (chúng ẩn) vì tôi tin rằng hoàn toàn có thể là bên trái là None trong khi bên phải là Node hoặc ngược lại, điều này sẽ gây ra mã gốc để ném một số AttributeError từ None không có phương thức depth.

Sửa

Để đối phó với những câu hỏi về <something> if <some condition> else <otherwise> khối:

Dòng cho <something> nếu <some condition> là đúng-y (coi là true), và <otherwise> nếu <some condition> là sai-y (được coi là sai)

Answer 2

Để rõ ràng, tôi khuyên bạn nên viết phương pháp depth như sau:

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

Lỗi xuất phát từ dòng này:

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

Bạn đang sử dụng chiều sâu như một chức năng và cố gắng để áp dụng nó vào các nút trái và phải. Bởi vì các nút trái và phải cũng là các nút, chúng có phương thức chiều sâu.

Bạn nên gọi phương thức sâu như thế này:

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

Tham số tự được ngầm truyền cho phương thức chiều sâu, nhưng sử dụng nó với các nhà điều hành chấm kể Python rằng phương pháp này thuộc về một trường hợp Node, và nó không phải là một số chức năng khác không bị ràng buộc với một đối tượng.

Answer 4

Bạn đã có bốn trường hợp để xem xét:

1. Cả hai subtrees đang trống.
2. Chỉ còn lại một cây con trái.
3. Chỉ cần một cây con bên phải trống.
4. Không có cây con nào trống.

Bạn đã bảo hiểm các trường hợp 1 và 4 nhưng đã bỏ lỡ 2 và 3. Bản sửa lỗi:

# 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