Duyệt in-order trong Tree JavaScript

Trong phương thức duyệt này, cây con trái được ghé thăm trước, sau đó nút gốc và sau đó cây con phải. Luôn nhớ rằng mỗi nút có thể đại diện cho một cây con.

Nếu một binary tree được duyệt in-order, đầu ra sẽ tạo ra các giá trị khóa được sắp xếp theo thứ tự tăng dần.

Bắt đầu từ A, theo in-order, ta chuyển sang cây con trái B. B cũng được duyệt in-order. Quá trình tiếp tục cho đến khi tất cả nút được ghé thăm. Kết quả inorder của cây này sẽ là:

D → B → E → A → F → C → G

Đây là thuật toán sẽ triển khai:

• Đệ quy duyệt cây con trái
• In dữ liệu của nút
• Đệ quy duyệt cây con phải

Hãy xem cách triển khai trong class. Vì không muốn người dùng tự truyền root, ta lại tạo hàm helper bên ngoài class.

inOrder() { inOrderHelper(this.root); }

Hàm helper:

Ví dụ

function inOrderHelper(root) {
  if (root !== null) {
    inOrderHelper(root.left);
    console.log(root.data);
    inOrderHelper(root.right);
  }
}

Bạn có thể kiểm tra bằng cách sau:

Ví dụ

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.inOrder();

Kết quả

Điều này sẽ cho ra kết quả:

3 5 7 10 12 15 50

Lưu ý rằng các phần tử được in theo thứ tự sắp xếp. Điều này là do vì ta đệ quy khám phá cây con trái trước, nên lấy được giá trị nhỏ nhất trước. Quá trình tiếp tục đến cuối và ta có tất cả phần tử theo thứ tự sắp xếp.