Hướng dẫn recursive tree traversal python - python duyệt cây đệ quy

Trong bài viết này, chúng tôi sẽ nghiên cứu những gì là truyền tải cây là gì và việc thực hiện các đường truyền trước, đặt hàng trước và cây bưu điện trong Python bằng cách sử dụng đệ quy. Đây là chủ đề quan trọng nhất để học trong khi học cấu trúc dữ liệu bằng Python. Chúng tôi cũng sẽ nghiên cứu các ví dụ và các đầu ra tương ứng cho cùng. & NBSP;

Nội dung chính Show

Cây truyền thống là gì?
Cây thứ tự truyền tải
Thuật toán cho việc truyền tải cây trước bằng cách sử dụng python
Mã Python cho việc đi ngang qua cây có đệ quy với đệ quy
Trực tiếp đặt hàng trước
Thuật toán cho việc đi qua cây trước bằng cách sử dụng Python
Mã Python cho việc đi ngang qua cây có đệ quy với đệ quy
Trực tiếp đặt hàng trước
Thuật toán cho việc đi qua cây trước bằng cách sử dụng Python
Mã Python cho & nbsp; Postorder & nbsp; TreeSalal với đệ quy
Độ phức tạp về thời gian
Sự kết luận

Cây truyền thống là gì?

Traversal là quá trình đi 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ư Danh sách Stack, Hàng đợi hoặc được liên kết thì việc đi qua các nút 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 tăng. Do đó, chúng tôi sử dụng các cấu trúc dữ liệu cây (đặc biệt là các cây nhị phân) khi chúng tôi phải thực hiện quá trình truyền tải và tìm các yếu tố dễ dàng. Sử dụng cấu trúc dữ liệu cây, nó trở nên dễ dàng để đi qua các nút so với các cấu trúc dữ liệu khác vì cây lưu trữ các yếu tố theo cấp bậc, và do đó, chúng ta có thể đi qua các yếu tố với mức độ ưu tiên và đường dẫn của chúng phù hợp. Bây giờ, có 3 phương pháp chính để đi qua cây trong Python với đệ quy sử dụng DFS là:

Inorder Traversal (trái, gốc, phải)
Truyền hàng trước Traversal (gốc, trái, phải)
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 đi qua cây và gọi chức năng nhiều lần cho đến khi chúng ta sẽ đi qua tất cả các nút của cây.

Ngoài ra, chúng ta cũng có thể tìm thấy sự đi ngang của 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à việc truyền tải cây trong Python mà không sử dụng quá trình đệ quy sử dụng cấu trúc dữ liệu ngăn xếp trong khi truyền tải 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 trên để đi qua cây trong Python với quá trình đệ quy:

Cây thứ tự truyền tải

Sử dụng phương pháp Inorder Traversal, trước tiên chúng tôi truy cập cây con bên trái của cây ban đầu. Sau đó, chúng tôi 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 việc truyền tải cây trước bằng cách sử dụng python

Gọi Stororder (bên trái-subtree)
Truy cập nút gốc
Gọi Inorder (Subtree đúng)

Ví dụ:

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

Bây giờ theo phương pháp truyền tải cây Inorder trong Python, trước tiên chúng tôi đi qua 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ẽ theo cùng một quy trình, tức là bên trái -> root -> phải nếu nút con trái của cây gốc có các nút con hơn nữa. Sau khi đi qua cây con bên trái, chúng tôi sẽ thêm kết quả vào mảng như hình dưới đây.

Sau khi làm theo bước đầu tiên, chúng tôi sẽ đi qua nút gốc của cây gốc như được hiển thị bên dưới.

Cuối cùng, chúng ta sẽ đi qua Subtree bên phải theo cùng một quy trình, tức là bên trái -> Root -> Phải nếu nút con bên phải của cây gốc có nhiều hơn một nút con.

Mã Python cho việc đi ngang qua cây có đệ quy 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))

Output:

[4, 2, 5, 1, 3]

Trực tiếp đặt hàng trước

Sử dụng phương pháp truyền tải trước, trước tiên chúng tôi truy cập gốc của cây gốc. Sau đó, chúng tôi 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 cho việc đi qua cây trước bằng cách sử dụng Python

Truy cập nút gốc
Gọi Inorder (Subtree đúng)
Ví dụ:

Ví dụ:

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

Sau khi làm theo bước đầu tiên, chúng tôi sẽ đi qua nút gốc của cây gốc như được hiển thị bên dưới.

Mã Python cho việc đi ngang qua cây có đệ quy 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))

Output:

[4, 2, 5, 1, 3]

Trực tiếp đặt hàng trước

Thuật toán cho việc đi qua cây trước bằng cách sử dụng Python

Calling left-subtree
Calling right-subtree
Gọi đặt hàng trước (bên trái-subtree)

Ví dụ:

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

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

Và cuối cùng, chúng tôi sẽ đi qua nút gốc của cây gốc và hoàn thành phương pháp truyền tải của chúng tôi như trong hình dưới đây.

Mã Python cho & nbsp; Postorder & nbsp; TreeSalal 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))

Output:

[4, 5, 2, 3, 1]

Độ phức tạp về thời gian

Ở đây, trong việc truyền tải cây trong Python bằng cách sử dụng đệ quy, độ phức tạp về thời gian là O (n) trong đó có n nút trong cây. Trong khi độ phức tạp không gian cũng là O (N) cho N nút có trong một mảng câu trả lời.

Đăng kí

Phương pháp truyền tải hàng đầu được sử dụng cho việc truyền tải cây để có được thứ tự không giải phóng các nút.
Phương pháp truyền tải trước được sử dụng để có được biểu thức tiền tố của cây biểu thức. Ngoài ra, Traversal Preversal giúp tạo ra một bản sao của cây.
Phương pháp truyền tải bưu chính được sử dụng để có được biểu thức postfix của cây biểu thức. Ngoài ra, phương pháp truyền tải bưu chính giúp xóa cây.

Sự kết luận

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