Duyệt post-order trong Tree JavaScript

Trong phương thức duyệt này, nút gốc được ghé thăm cuối cùng, do đó có tên post-order. Trước tiên duyệt cây con trái, rồi cây con phải và cuối cùng nút gốc.

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

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

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

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

Hãy xem cách triển khai trong class:

postOrder() {
  postOrderHelper(this.root);
}

Hàm helper:

Ví dụ

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

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.postOrder();

Kết quả

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

3 7 5 12 50 15 10