Khám phá tính năng duyệt cây trong JavaScript: Đặt hàng trước, đặt hàng trước và đặt hàng sau với các ví dụ

Duyệt cây là một khái niệm cơ bản trong khoa học máy tính liên quan đến việc truy cập một cách có hệ thống từng nút trong cấu trúc dữ liệu cây. Thông qua duyệt cây, chúng ta có thể xử lý các nút theo thứ tự định trước, tạo điều kiện thuận lợi cho các hoạt động như tìm kiếm, sắp xếp và đánh giá các biểu thức.

Trong bài viết này, chúng ta sẽ khám phá ba trong số các phương pháp duyệt cây được sử dụng rộng rãi nhất: thứ tự, thứ tự trước và thứ tự sau.

Thông qua các ví dụ rõ ràng và ngắn gọn được triển khai bằng JavaScript, bạn sẽ hiểu rõ hơn về các kỹ thuật truyền tải này.

Định nghĩa cấu trúc cây

Trước khi đi sâu vào các thuật toán duyệt cây, hãy xác định cấu trúc mà chúng ta sẽ sử dụng cho cây nhị phân. Cây sẽ bao gồm các nút, trong đó mỗi nút chứa một giá trị và tham chiếu đến các nút con bên trái và bên phải của nó.

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

Bây giờ chúng ta đã xác định cấu trúc cây, chúng ta có thể tiến hành khám phá ba phương pháp duyệt cây.

Truyền đơn đặt hàng

Duyệt theo thứ tự tuân theo mô hình tiếp theo của việc truy cập các nút trong cây nhị phân - đầu tiên thuật toán duyệt qua cây con bên trái, sau đó duyệt qua nút hiện tại và cuối cùng duyệt qua cây con bên phải. Điều này đảm bảo rằng các nút được truy cập theo thứ tự tăng dần nếu cây đại diện cho cấu trúc dữ liệu được sắp xếp.

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

Truyền tải thứ tự đệ quy

1. Kiểm tra xem nút hiện tại có rỗng không. Nếu vậy, trở lại.

   
   

2. Gọi đệ quy hàm trên cây con bên trái.

   
   

3. Ghé thăm nút hiện tại.

   
   

4. Gọi đệ quy hàm trên cây con bên phải.

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

Truyền tải thứ tự không đệ quy

1. Khởi tạo một ngăn xếp trống và đặt nút hiện tại thành gốc của cây.

   
   

2. Lặp lại trong khi ngăn xếp không trống hoặc nút hiện tại không rỗng.

   • Đẩy tất cả các nút bên trái vào ngăn xếp cho đến khi đạt đến nút con bên trái rỗng.

   • Lấy một nút từ ngăn xếp, truy cập nó và đặt nút hiện tại thành nút con bên phải của nó.

     
     

3. Lặp lại bước 2 cho đến khi ngăn xếp trống và nút hiện tại là null.

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

Truyền tải đặt hàng trước

Trong quá trình duyệt theo thứ tự trước, thuật toán đầu tiên truy cập nút hiện tại, sau đó duyệt qua cây con bên trái và cuối cùng duyệt qua cây con bên phải. Thứ tự này đảm bảo rằng các nút được truy cập theo cách "từ trên xuống", bắt đầu từ gốc và di chuyển về phía các lá.

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

Đệ quy Preorder Traversal

1. Kiểm tra xem nút hiện tại có rỗng không. Nếu vậy, trở lại.

   
   

2. Ghé thăm nút hiện tại.

   
   

3. Gọi đệ quy hàm trên cây con bên trái.

   
   

4. Gọi đệ quy hàm trên cây con bên phải.

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

Truyền tải đơn đặt hàng trước không đệ quy

1. Bắt đầu với một ngăn xếp trống và đẩy nút gốc vào ngăn xếp.

   
   

2. Khởi tạo một mảng trống để lưu trữ kết quả duyệt theo đơn đặt hàng trước.

   
   

3. Nhập vòng lặp while chạy cho đến khi ngăn xếp trống.

   
   

4. Lấy một nút từ ngăn xếp và truy cập nút đó bằng cách thêm giá trị của nó vào mảng kết quả.

   
   

5. Nếu nút có con bên phải, hãy đẩy con bên phải vào ngăn xếp.

   
   

6. Nếu nút có con bên trái, hãy đẩy con bên trái vào ngăn xếp.

   
   

7. Lặp lại các bước 3-6 cho đến khi ngăn xếp trống.

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

Truyền tải sau khi đặt hàng

Trong quá trình duyệt này, đầu tiên thuật toán duyệt cây con bên trái, sau đó duyệt cây con bên phải và cuối cùng thăm nút hiện tại. Thứ tự này đảm bảo rằng các nút được truy cập theo cách "từ dưới lên", bắt đầu từ các lá và di chuyển về phía gốc.

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

Truyền tải theo thứ tự đệ quy

1. Kiểm tra xem nút hiện tại có rỗng không. Nếu vậy, trở lại.

   
   

2. Gọi đệ quy hàm trên cây con bên trái.

   
   

3. Gọi đệ quy hàm trên cây con bên phải.

   
   

4. Ghé thăm nút hiện tại.

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

Truyền tải theo thứ tự không đệ quy

1. Bắt đầu với một ngăn xếp trống và đẩy nút gốc vào ngăn xếp.

   
   

2. Khởi tạo một mảng trống để lưu trữ kết quả duyệt theo thứ tự sau.

   
   

3. Nhập vòng lặp while chạy cho đến khi ngăn xếp trống.

   
   

4. Lấy nút trên cùng từ ngăn xếp (không xóa nó).

   
   

5. Nếu nút có một nút con bên trái, hãy đẩy nút con bên trái vào ngăn xếp và đặt nút con bên trái của nút hiện tại thành null.

   
   

6. Nếu nút có con bên phải, hãy đẩy con bên phải vào ngăn xếp và đặt con bên phải của nút hiện tại thành null.

   
   

7. Nếu nút không có con trái hay con phải thì đó là nút lá. Lấy nút ra khỏi ngăn xếp và thêm giá trị của nó vào mảng kết quả.

   
   

8. Lặp lại các bước 4-7 cho đến khi ngăn xếp trống.

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

Phần kết luận

Tôi hy vọng rằng bây giờ bạn đã hiểu rõ về sự khác biệt giữa truyền tải theo thứ tự, đặt hàng trước và sau khi đặt hàng trong JavaScript. Với kiến thức và các ví dụ được cung cấp, giờ đây bạn đã được trang bị để áp dụng các kỹ thuật này vào các nhiệm vụ và dự án của riêng mình một cách hiệu quả.