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. Show
Mã số
đầu ra 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à
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
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 đệ quyclass 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 TraversSử 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
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 đệ quyclass 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 TraversalSử 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
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 đệ quyclass 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í
Phần kết luậnDo đó, 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?Hầu hết mọi người sử dụng cây nhị phân để thực hiện sắp xếp chèn hiệu quả. Nếu không, họ sẽ sử dụng một bộ sưu tập. Để in theo thứ tự đã sắp xếp, bạn nên lặp lại bên trái, in nút, sau đó lặp lại bên phải .
Làm cách nào để tìm kiếm cây nhị phân mà không cần đệ quy?Phương pháp không đệ quy. Thêm gốc vào hàng đợi . Kiểm tra xem nút hiện tại có phần tử chúng ta đang tìm kiếm không nếu có thì trả về true nếu không thêm các nút con của nút hiện tại vào hàng đợi. Nếu hàng đợi trống, có nghĩa là chúng tôi chưa tìm thấy phần tử.
Các vòng lặp có được phép trong cây không?Cây không có nhiều cạnh và không có vòng lặp . |