Lặp qua python cây nhị phân

Triển khai cây tìm kiếm nhị phân trong Python bằng vòng lặp while. Đoạn mã sau cho biết cách triển khai cây tìm kiếm nhị phân [BST] bằng ngôn ngữ lập trình Python.  

Mã số

class Node:
    def __init__[self, node_data]:
        self.node_data = node_data
        self.left_node = None
        self.right_node = None

    def __repr__[self]:
        return repr[self.node_data]


class Tree:
    def __init__[self]:
        self.root = None

    # Insert a node to the tree
    def insert[self, node_data]:
        if self.root is None:
            self.root = Node[node_data]
            return

        current_node = self.root
        prev_node = None

        while current_node:
            prev_node = current_node
            if node_data < current_node.node_data:
                current_node = current_node.left_node
            else:
                current_node = current_node.right_node

        if node_data < prev_node.node_data:
            prev_node.left_node = Node[node_data]
        else:
            prev_node.right_node = Node[node_data]

    # Build the tree
    def build_tree[self]:
        for x in [7, 6, 8, 5, 9, 2, 12, 3]:
            self.insert[x]

    # Print the tree
    def in_order[self, node]:
        if node.left_node:
            self.in_order[node.left_node]
        print[node, end=' ']
        if node.right_node:
            self.in_order[node.right_node]

    # Search in tree
    def search_bst[self, node, key]:
        while node is not None:
            if node.node_data == key:
                return node
            if key < node.node_data:
                node = node.left_node
            else:
                node = node.right_node

        return 'Not found'


if __name__ == '__main__':
    my_tree = Tree[]
    my_tree.build_tree[]

    my_tree.in_order[my_tree.root]
    print['\nSearch node_data']
    print[my_tree.search_bst[my_tree.root, 2]]
    print[my_tree.search_bst[my_tree.root, 15]]
    print['']

đầu ra

2 3 5 6 7 8 9 12 
Search node_data
2
Not found

Truyền tải là quá trình duyệt qua nút của cấu trúc dữ liệu. Nhưng nếu chúng ta sử dụng cấu trúc dữ liệu như ngăn xếp, hàng đợi hoặc danh sách được liên kết thì việc duyệt qua các nút sẽ trở nên khó khăn vì cấu trúc dữ liệu này là tuyến tính và do đó độ phức tạp của thời gian duyệt tăng lên. Do đó, chúng ta sử dụng cấu trúc dữ liệu cây [đặc biệt là cây nhị phân] khi phải thực hiện quá trình truyền tải và tìm các phần tử một cách dễ dàng. Sử dụng cấu trúc dữ liệu cây, việc duyệt qua các nút trở nên dễ dàng hơn so với các cấu trúc dữ liệu khác vì cây lưu trữ các phần tử theo thứ bậc và do đó, chúng ta có thể duyệt qua các phần tử với mức độ ưu tiên và đường dẫn phù hợp. Bây giờ, có 3 phương pháp chính để duyệt cây trong python với đệ quy bằng DFS, đó là

1. Inorder Traversal [trái, gốc, phải]
2. Preorder Traversal [gốc, trái, phải]
3. Postorder Traversal [trái, phải, gốc]

Hãy nhớ rằng chúng ta sẽ sử dụng hàm đệ quy trong khi duyệt qua cây và gọi hàm này lặp đi lặp lại cho đến khi chúng ta duyệt qua tất cả các nút của cây

Ngoài ra, chúng ta cũng có thể tìm duyệt cây mà không cần sử dụng phương pháp đệ quy. Sự khác biệt duy nhất giữa hai phương pháp này là duyệt cây trong python mà không sử dụng quy trình đệ quy sử dụng cấu trúc dữ liệu ngăn xếp trong khi duyệt cây trong python với đệ quy sử dụng cấu trúc dữ liệu mảng

Bây giờ chúng ta hãy nghiên cứu các phương pháp duyệt cây ở trên trong python với quy trình đệ quy

Duyệt cây theo thứ tự

Sử dụng phương pháp duyệt theo thứ tự, đầu tiên chúng ta thăm cây con bên trái của cây ban đầu. Sau đó, chúng ta sẽ đi qua nút gốc của cây và cuối cùng là cây con bên phải của cây ban đầu

Thuật toán cho Inorder Tree Traversal bằng Python

1. Lệnh gọi [cây con bên trái]
2. Ghé thăm nút gốc
3. Calling Inorder [cây con bên phải]

Ví dụ

Chúng ta hãy xem xét cây nhị phân sau

Bây giờ, theo phương pháp duyệt cây theo thứ tự trong python, trước tiên chúng ta duyệt cây con bên trái của cây ban đầu. Hãy nhớ rằng, ngay cả khi đi qua cây con bên trái, chúng ta sẽ thực hiện theo cùng một quy trình. trái -> gốc -> phải nếu nút con bên trái của cây gốc có thêm các nút con. Sau khi duyệt cây con bên trái ta sẽ cộng kết quả vào mảng như hình bên dưới

Sau khi làm theo bước đầu tiên, chúng ta sẽ đi qua nút gốc của cây ban đầu như hình bên dưới

Cuối cùng, chúng ta sẽ duyệt cây con bên phải theo quy trình tương tự. trái -> gốc -> phải nếu nút con bên phải của cây ban đầu có nhiều hơn một nút con

Mã Python cho Inorder Tree Travers với đệ quy

class TreeNode:
    def __init__[self, val]:
        self.val = val
        self.left = None
        self.right = None 

def inorderTraversal[root]:
    answer = []

    inorderTraversalUtil[root, answer]
    return answer

def inorderTraversalUtil[root, answer]:

    if root is None:
        return

    inorderTraversalUtil[root.left, answer]
    answer.append[root.val]
    inorderTraversalUtil[root.right, answer]
    return

root = TreeNode[1]
root.left = TreeNode[2]
root.right = TreeNode[3]
root.left.left = TreeNode[4]
root.left.right = TreeNode[5]

print[inorderTraversal[root]]

đầu ra

[4, 2, 5, 1, 3]

Đặt hàng trước Tree Travers

Sử dụng phương pháp duyệt theo thứ tự trước, trước tiên chúng tôi truy cập vào gốc của cây ban đầu. Sau đó, chúng ta sẽ đi qua cây con bên trái của cây ban đầu và cuối cùng là cây con bên phải của cây ban đầu

Thuật toán Preorder Tree Traversal sử dụng Python

1. Ghé thăm nút gốc
2. Đặt hàng trước cuộc gọi [cây con bên trái]
3. Đặt hàng trước cuộc gọi [cây con bên phải]

Ví dụ

Chúng ta hãy xem xét cây ví dụ sau

Theo phương pháp duyệt theo thứ tự trước, đầu tiên chúng ta sẽ duyệt qua nút gốc của cây ban đầu và đưa nó vào mảng kết quả như trong hình bên dưới

Sau đó, chúng ta sẽ duyệt cây con bên trái của cây ban đầu bằng cách gọi phương thức duyệt theo thứ tự trước. Ở đây chúng ta sẽ gọi hàm preorder một cách đệ quy để duy trì cùng một quá trình duyệt i. e root -> left -> right nếu con trái của cây ban đầu có nhiều hơn một nút con và thêm câu trả lời vào mảng như trong hình bên dưới

Cuối cùng, chúng ta sẽ duyệt cây con bên phải của cây ban đầu tương tự như chúng ta đã làm với cây con bên trái và đưa kết quả vào mảng trả lời như hình bên dưới

Mã Python của Preorder Tree Traversal với đệ quy

class TreeNode:

    def __init__[self,val]:
        self.val = val
        self.left = None
        self.right = None

def preorderTraversal[root]:
    answer = []

    preorderTraversalUtil[root, answer]
    return answer

def preorderTraversalUtil[root, answer]:

    if root is None:
        return 

    answer.append[root.val]

    preorderTraversalUtil[root.left, answer]

    preorderTraversalUtil[root.right, answer]

    return

root = TreeNode[1]
root.left = TreeNode[2]
root.right = TreeNode[3]
root.left.left = TreeNode[4]
root.left.right = TreeNode[5]

print[preorderTraversal[root]]

đầu ra

[1, 2, 4, 5, 3]

Postorder Tree Traversal

Sử dụng phương pháp duyệt cây theo thứ tự sau, trước tiên chúng ta truy cập cây con bên trái của cây ban đầu, tiếp theo là cây con bên phải và cuối cùng là nút gốc của cây ban đầu

Thuật toán duyệt cây theo thứ tự sau bằng Python

1. Gọi cây con bên trái
2. Gọi phải-cây con
3. Truy cập nút gốc

Ví dụ

Chúng ta hãy xem xét cây ví dụ sau

Sử dụng phương pháp duyệt theo thứ tự sau, trước tiên chúng ta sẽ duyệt cây con bên trái của cây ban đầu. Hãy nhớ rằng chúng ta sẽ thực hiện theo cùng một quá trình duyệt cây con bên trái i. e left -> right -> root nếu cây con bên trái có nhiều hơn 1 nút con rồi đưa kết quả vào mảng trả lời như trong hình

Sau đó, chúng ta sẽ duyệt cây con bên phải của cây ban đầu tương tự như chúng ta đã làm với cây con bên trái và thêm câu trả lời vào mảng kết quả như hình bên dưới

Và cuối cùng, chúng ta sẽ duyệt qua nút gốc của cây ban đầu và kết thúc phương thức duyệt của chúng ta như trong hình bên dưới

Mã Python cho Truyền tải cây đặt hàng sau với đệ quy

class TreeNode:

    def __init__[self, val]:
        self.val = val
        self.left = None
        self.right = None

def postorderTraversal[root]:
    answer = []

    postorderTraversalUtil[root, answer]
    return answer

def postorderTraversalUtil[root, answer]:

    if root is None:
        return

    postorderTraversalUtil[root.left, answer]

    postorderTraversalUtil[root.right, answer]

    answer.append[root.val]

    return

root = TreeNode[1]
root.left = TreeNode[2]
root.right = TreeNode[3]
root.left.left = TreeNode[4]
root.left.right = TreeNode[5]

print[postorderTraversal[root]]

đầu ra

[4, 5, 2, 3, 1]

Thời gian phức tạp

Ở đây, khi duyệt cây trong python sử dụng đệ quy, độ phức tạp thời gian là O[n] trong đó có n nút trong cây. Trong khi độ phức tạp của không gian cũng là O[n] đối với n nút có trong một mảng câu trả lời

Đăng kí

1. Phương pháp duyệt theo thứ tự được sử dụng để duyệt cây để lấy thứ tự không giảm dần của các nút
2. Phương pháp duyệt theo thứ tự trước được sử dụng để lấy biểu thức tiền tố của cây biểu thức. Ngoài ra, duyệt theo thứ tự trước giúp tạo một bản sao của cây
3. Phương thức duyệt theo thứ tự sau được sử dụng để lấy biểu thức hậu tố của cây biểu thức. Ngoài ra, phương pháp duyệt theo thứ tự sau giúp xóa cây

Phần kết luận

Do đó, việc học và hiểu ứng dụng và cách sử dụng duyệt cây trong thế giới thực chứng tỏ rằng đây là một chủ đề quan trọng cần nghiên cứu đối với bất kỳ lập trình viên nào. Vì vậy, trong bài viết trên, chúng ta đã nghiên cứu về duyệt cây trong python sử dụng đệ quy và các phương pháp duyệt cây có tính chất đệ quy. Ngoài ra, chúng tôi đã nghiên cứu mã python để duyệt cây và đầu ra tương ứng của nó

Bạn có thể lặp qua cây nhị phân không?

Làm cách nào để tìm kiếm cây nhị phân mà không cần đệ quy?

Các vòng lặp có được phép trong cây không?