Specify the correct implementation of pre-order traverse algorithm for binary trees.

Đáp án đúng: "

void preOrder(Node p) {
  if (p != null) {
    visit(p);
    preOrder(p.left);
    preOrder(p.right);
  }
}

". Tiền thứ tự nghĩa là thăm gốc trước rồi mới xuống nhánh trái, sau đó nhánh phải, nên lệnh thăm phải đứng trước cả hai lời gọi đệ quy; thêm vào đó điều kiện p khác null chính là chỗ dừng, nó chặn lời gọi đi vào cây rỗng. Cách viết "

void preOrder(Node p) {
  if (p != null) {
    preOrder(p.left);
    visit(p);
    preOrder(p.right);
  }
}

" đặt lệnh thăm giữa hai lời gọi nên cho ra thứ tự trung tố, với cây tìm kiếm thì in dãy tăng dần chứ không phải tiền thứ tự. Cách viết "

void preOrder(Node p) {
  if (p == null) {
    visit(p);
    preOrder(p.left);
    preOrder(p.right);
  }
}

" đảo điều kiện thành p bằng null, tức chỉ làm việc khi con trỏ rỗng, nên nó thăm một nút không tồn tại và không bao giờ đi xuống cây thật. Cách viết "

void preOrder(Node p) {
  visit(p);
  preOrder(p.left);
  preOrder(p.right);
}

" đúng trật tự thăm nhưng bỏ hẳn chỗ dừng, mỗi lá vẫn gọi tiếp vào hai con rỗng nên đệ quy lún vô hạn và chương trình đổ vì truy cập trên con trỏ rỗng.