Hướng dẫn find height binary tree python - tìm chiều cao cây nhị phân python

Cây nhị phân là một cấu trúc dữ liệu duy nhất được áp dụng cho các sơ đồ lưu trữ dữ liệu trong lĩnh vực khoa học máy tính. Mỗi nút trong một cây nhị phân có thể có nhiều nhất là hai đứa trẻ. Sử dụng cấu trúc dữ liệu cây nhị phân có lợi vì nó có lợi ích của cả một mảng được đặt hàng và danh sách được liên kết, do đó, độ phức tạp thời gian cho tìm kiếm nhanh như trong một mảng được sắp xếp và các hoạt động chèn hoặc xóa nhanh như trong một Danh sách liên kết. Ví dụ về một cây nhị phân: & nbsp;

Làm thế nào để tìm chiều cao của một cây nhị phân?

Chiều cao của cây nhị phân được coi là đường dẫn dài nhất bắt đầu từ nút gốc đến bất kỳ nút lá nào trong cây nhị phân. Nếu nút mục tiêu mà chúng ta phải tính chiều cao, không có bất kỳ nút nào khác được kết nối với nó, thì kết quả là chiều cao của nút đó sẽ là 0. Do đó, chúng ta có thể nói rằng chiều cao của cây nhị phân là độ cao từ Nút gốc trong toàn bộ cây nhị phân. Theo thuật ngữ của Layman, chiều cao của một cây nhị phân tương đương với số lượng lớn nhất của các cạnh bắt đầu từ gốc đến nút lá thưa thớt nhất trong cây nhị phân.

Một khái niệm liên quan trong cấu trúc dữ liệu cây nhị phân là độ sâu của cây. Theo định nghĩa về độ sâu của một nút trong cây nhị phân là tổng lượng các cạnh bắt đầu từ nút gốc đến nút đích. Hơn nữa, độ sâu của cây nhị phân là tổng lượng các cạnh bắt đầu từ nút gốc đến nút lá xa nhất. Và trong bài viết này, chúng ta sẽ học cách tìm độ sâu/độ sâu tối đa của cây nhị phân bằng cách sử dụng đệ quy và không sử dụng đệ quy. & Nbsp;

Thí dụ

Hình dưới đây cho thấy một cây nhị phân với 4 cấp độ được chỉ định. & NBSP;

Các nút lá của cây nhị phân là: [70, 80, 50, 90] & nbsp;[70, 80, 50, 90] 

Đối với nút lá 70, số lượng nút dọc theo các cạnh là 4. & nbsp;

Đối với nút lá 80, số lượng nút dọc theo các cạnh là 4. & nbsp;

Đối với nút lá 50, số lượng nút dọc theo các cạnh là 3. & nbsp;

Đối với nút lá 90, số lượng nút dọc theo các cạnh là 4.

Số lượng nút tối đa từ gốc đến xa nhất là: Max (4, 4, 3, 4) là 4. Do đó, chiều cao của cây nhị phân là 4. & nbsp;height of the binary tree is 4. 

Thuật toán tính chiều cao của cây nhị phân

Có hai phương pháp để tiếp cận tuyên bố vấn đề này. Cách tiếp cận đầu tiên dựa trên độ sâu đầu tiên bằng cách sử dụng đệ quy và phương pháp khác dựa trên tìm kiếm đầu tiên bằng chiều rộng bằng cách sử dụng Traversal theo thứ tự cấp mà không sử dụng đệ quy. & NBSP;Depth first seach using recursion, and the other method is based on Breadth first search using Level order traversal without using recursion. 

Tìm chiều cao với đệ quy (phương pháp tìm kiếm đầu tiên sâu)

Chúng ta hãy xem xét một ví dụ để hiểu cách tiếp cận theo cách dễ dàng hơn. Hãy xem xét các cây nhị phân sau đây, với ‘A, là nút gốc và‘ h, ’e,’ f, và ’g, là nút lá: & nbsp;

Đối với nút lá ‘H, số lượng nút dọc theo các cạnh là 4. & nbsp;

Đối với nút lá ‘E, số lượng các nút dọc theo các cạnh là 3. & nbsp;

Đối với nút lá ‘F, số lượng nút dọc theo các cạnh là 3. & nbsp;

Đối với nút lá ‘G, số lượng nút dọc theo các cạnh là 3.

Số lượng nút tối đa từ gốc đến xa nhất là: Max (4, 3, 3, 3) là 4. Do đó, chiều cao của cây nhị phân là 4. & nbsp;Hence, height of the binary tree is 4. 

Hãy để chúng tôi thảo luận về việc thực hiện từng bước & NBSP;

Bước 1: Hỏi nút gốc, chiều cao của cây nhị phân là bao nhiêu nếu nút gốc là 'A' và đệ quy nút gốc hỏi cùng một câu hỏi bên trái là 'B' và đứa trẻ bên phải là 'C' . Và v.v. & nbsp; & nbsp; Ask the root node, what is the height of the binary tree if the root node is ‘a’, and recursively the root node asks the same question to its left which is ‘b’ and right child which is ‘c’. And so on.  

Bước 2: Kiếm 'B' sẽ làm giống như nút 'A' và hỏi đứa con trái của nó 'D' và đứa trẻ bên phải 'e' sẽ là chiều cao nếu bạn là nút gốc của cây nhị phân hiện tại, tức là . & nbsp;Recursively ‘b’ will do the same as the node ‘a’ and ask its left child ‘d’ and the right child ‘e’ what will be the height if you are the root node of the current binary tree, ie. 

Bước 3: Nút ‘D, hỏi các câu hỏi tương tự với nó, con trái và phải là con. & NBSP;The node ‘d’ asks the same questions to it’s left and right child ie. 

Nút ‘H, làm điều tương tự và bây giờ kể từ nút bên trái của‘ H, là NULL, nó trả về 0. & nbsp;

Bước 4: nút ‘H, đưa ra kết quả của đứa con trái và phải của nó, và sau khi chúng tôi tìm thấy độ dài tối đa giữa Leftheight và Rightheight, trong đó: & nbsp;The node ‘h’ gives out the result of its left and right child, and after we find the maximum length between the leftHeight and rightHeight, where : 

leftheight = 0 & nbsp;

rightheight = 0

tối đa (0, 0) = 0 & nbsp;

Do đó, tại mỗi lần lặp, nút sẽ trả về độ dài: 1 + tối đa (leftheight, rightheight)1 + max(leftHeight, rightHeight)

Bước 5: Để có được trực giác tốt hơn của thuật toán, hãy tham khảo hình ảnh sau:To get a better intuition of the algorithm, refer to the following image:

& nbsp; mã python (với đệ quy): & nbsp;

# define a Class Tree, to intiate the binary tree
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
def height(root):
 
    # Check if the binary tree is empty
    if root is None:
        # If TRUE return 0
        return 0 
    # Recursively call height of each node
    leftAns = height(root.left)
    rightAns = height(root.right)
 
    # Return max(leftHeight, rightHeight) at each iteration
    return max(leftAns, rightAns) + 1
 
# Test the algorithm
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
 
print("Height of the binary tree is: " + str(height(root)))

Đầu ra: Chiều cao của một cây nhị phân đơn giản:

Chiều cao của cây nhị phân là: 3

Sự phức tạp về thời gian và không gian:

Độ phức tạp về thời gian của thuật toán là O (n) khi chúng ta lặp qua nút của cây nhị phân, việc tính chiều cao của cây nhị phân chỉ một lần.

Và độ phức tạp không gian cũng là O (n) vì chúng ta đang theo đệ quy, trong đó ngăn xếp đệ quy có thể có tối đa các yếu tố N. & nbsp;

Trong đó n là số lượng nút trong cây nhị phân.

Tìm chiều cao mà không có đệ quy (phương pháp tìm kiếm đầu tiên)

Chúng ta hãy xem xét một ví dụ để hiểu cách tiếp cận theo cách dễ dàng hơn. Hãy xem xét cây nhị phân sau, với 12 là nút gốc và 19, 16, 7 và 8 là nút lá: & nbsp;

Đối với nút lá 19, số lượng nút dọc theo các cạnh là 4. & nbsp;

Đối với nút lá 16, số lượng nút dọc theo các cạnh là 3. & nbsp;

Đối với nút lá 7, số lượng nút dọc theo các cạnh là 3. & nbsp;

Đối với nút lá 8, số lượng nút dọc theo các cạnh là 3.

Số lượng nút tối đa từ gốc đến xa nhất là: Max (4, 3, 3, 3) là 4. Do đó, chiều cao của cây nhị phân là 4. & nbsp; & nbsp;Hence, height of the binary tree is 4.  

Hãy để chúng tôi thảo luận về việc thực hiện từng bước & NBSP;

Bước 1: Sử dụng cấu trúc dữ liệu hàng đợi để tiếp cận tuyên bố vấn đề này, do đó, khởi tạo cấu trúc dữ liệu hàng đợi trống. & nbsp; Use a queue data structure to approach this problem statement, hence, initialize an empty queue data structure.  

Đặt biến ANS ANS thành 0. & nbsp;

ANS = 0 & nbsp;

Bước 2: Nút gốc Enqueue cho hàng đợi và xử lý nó trong một vòng lặp lại cho đến khi không còn phần tử và thực hiện quy trình tương tự cho các nút khác, tức là. & NBSP; & nbsp;Enqueue root node to the queue and process it in a while loop until there are no elements left and perform the same process for the other nodes, ie.  

Nút gốc enqueue 12 & nbsp; 

Currsize = 1

Bước 3: Chạy vòng lặp một thời gian cho đến khi vurrsize = 0, và cho đến khi đó tiếp tục các phần tử khử màu và sau khi xử lý các phần tử khi giá trị của currsize = 0, tăng giá trị của ANSRun a while loop until currSize = 0, and till then keep dequeuing elements and after processing the elements when the value of currSize = 0, increment the value of ans

Do đó, Dequeue 12, và kiểm tra đứa con trái của nó là 13 và đứa con phải là 14, và làm chúng

Now:

Currsize = 0

Currnode = 12

Kể từ đó, Currsize = 0

ANS = 1 & nbsp; 

Ở lần lặp tiếp theo, Currsize = 2 & nbsp; 

Dequeue 13 và lặp lại các bước 2 và 3 & nbsp;steps 2 and 3 

Now:   

Currsize = 1

Bước 3: Chạy vòng lặp một thời gian cho đến khi vurrsize = 0, và cho đến khi đó tiếp tục các phần tử khử màu và sau khi xử lý các phần tử khi giá trị của currsize = 0, tăng giá trị của ANS 

Do đó, Dequeue 12, và kiểm tra đứa con trái của nó là 13 và đứa con phải là 14, và làm chúngsteps 2 and 3 

Now: 

Currsize = 0

Currnode = 12 

Kể từ đó, Currsize = 0

ANS = 1 & nbsp; 

Ở lần lặp tiếp theo, Currsize = 2 & nbsp;

Dequeue 13 và lặp lại các bước 2 và 3 & nbsp;

Currnode = 13 & nbsp;

Một lần nữa, dequeue 14 và lặp lại các bước 2 và 3 & nbsp;

# Import Collections libaray to use Queue Datastructure
import collections
 
# define a Class Tree, to intiate the binary tree
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
def height(root):
    # Set result variable to 0
    ans = 0
    # Initialise the queue
    queue = collections.deque()
    # Check if the tree has no nodes
    if root is None:
        return ans
 
    # Append the nodes to queue and process it in while loop until its empty
    queue.append(root)
 
    # Process in while loop until there are elements in queue
 
    while queue:
        currSize = len(queue)
        # Unless the queue is empty
        while currSize > 0:
            # Pop elements one-by-one
            currNode = queue.popleft()
            currSize -= 1
 
            # Check if the node has left/right child
            if currNode.left is not None:
                queue.append(currNode.left)
            if currNode.right is not None:
                queue.append(currNode.right)
 
        # Increment ans when currSize = 0
        ans += 1
    return ans
 
# Test the algorithm
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
 
print("Height of the binary tree is: " + str(height(root)))

Currnode = 14 & nbsp;

ANS = 2 & nbsp;

Thực hiện theo, các bước lặp đi lặp lại cho đến khi không có nút để đưa vào hàng đợi, sau tất cả các bước & nbsp;

ANS = 4 & nbsp;

Do đó, chúng tôi nhận được ANS = 4, IE chiều cao của cây nhị phân là 4.

Mã Python (không có đệ quy): & nbsp;

Đầu ra: Chiều cao của một cây nhị phân đơn giản:

1. Chiều cao của cây nhị phân là: 3
2. Sự phức tạp về thời gian và không gian:
3. Độ phức tạp về thời gian của thuật toán là O (n) khi chúng ta lặp qua nút của cây nhị phân, việc tính chiều cao của cây nhị phân chỉ một lần.
4. Và độ phức tạp không gian cũng là O (n) vì chúng ta đang sử dụng một không gian bổ sung cho hàng đợi. & Nbsp;

Conclusion:

Trong đó n là số lượng nút trong cây nhị phân.

Làm thế nào để bạn tìm thấy chiều cao của một cây nhị phân trong Python?

Làm thế nào để bạn tìm thấy chiều cao của một cây nhị phân?

Làm thế nào để bạn tính toán chiều cao của một cây?

Chiều cao của cây trong cây nhị phân là bao nhiêu?