Kết hợp Iterator và Composite duyệt cây đệ quy

Giới thiệu

Bài này học bộ duyệt ngoài cho cây thực đơn. Bạn dùng nó để lọc món chay mà không sửa cây.

Kiến thức cần nhớ

Vì sao cần Iterator ngoài

• Gọi in đệ quy từ trong thì in hết, không lọc được.
• Nhồi lọc vào cụm khiến cụm lo việc không phải của nó.
• Cần bộ duyệt ngoài nhả từng món cho phục vụ tự quyết.
• Ví dụ đời thường: như cần người dẫn tour chỉ từng phòng thay vì loa phát cả nhà.

Bộ duyệt ngăn xếp

• Giữ 1 ngăn các bộ duyệt con đang dang dở.
• Lấy tiếp: lấy món kế trên đỉnh, gặp cụm thì đẩy bộ của nó vào.
• Lượt đi sâu dần từng nhánh: hết nhánh này mới sang nhánh khác.
• Ví dụ đời thường: như đi hết 1 dãy siêu thị rồi mới sang dãy khác.

Phục vụ dùng bộ duyệt

• Xin bộ duyệt từ thực đơn tổng rồi lặp hỏi còn không.
• Mỗi món nhận được thì kiểm tra chay rồi in nếu đạt.
• Phục vụ không cần biết cụm hay lá, cây sâu mấy tầng.
• Mọi hiểu biết về cây nằm gọn trong bộ duyệt.

Ví dụ

• Input: duyệt toàn bộ cây 3 tầng. Output: mọi món ra đúng 1 lần, cha trước con.
• Giải thích: ngăn xếp đảm bảo đi sâu dần theo thứ tự.
• Input: lọc món chay trên cây. Output: chỉ món chay được in.
• Giải thích: phục vụ kiểm tra từng món bộ duyệt nhả ra.

💻 Bài tập

Ngôn ngữ: C++17 (hoặc Java). Dùng cây thực đơn ngày 67. Nộp vào day-068/.

Bài 1: CompositeIterator bằng stack

class CompositeIterator : public Iterator<std::shared_ptr<MenuComponent>> {
 public:
  explicit CompositeIterator(std::unique_ptr<Iterator<std::shared_ptr<MenuComponent>>> root);
  bool hasNext() const override;
  std::shared_ptr<MenuComponent> next() override;   // gặp Menu thì đẩy iterator của nó vào stack
};

MenuItem::createIterator() trả NullIterator (luôn hasNext() == false).

Duyệt cây ngày 67 -> mọi thành phần (cả Menu và MenuItem) ra đúng 1 lần, cha trước con
Số phần tử duyệt được = countItems() + số Menu con

Bài 2: Phục vụ lọc món chay

Waitress::printVegetarianMenu() dùng CompositeIterator. Chỉ gọi vegetarian() trên MenuItem, bỏ qua Menu mà không dùng try/catch làm luồng điều khiển.

Thêm 2 bộ lọc: printCheaperThan(double) và printByKeyword(std::string). Cả 3 hàm dùng chung 1 hàm duyệt nhận std::function<bool(const MenuItem&)>.

Bài 3: Duyệt theo chiều rộng và duyệt lười (nâng cao)

1. Viết BreadthFirstIterator dùng queue. In thứ tự của 2 iterator trên cùng cây, chỉ ra khác biệt.
2. Viết bản duyệt bằng C++20 coroutine (std::generator nếu có, hoặc tự viết generator tối giản), hoặc bằng generator Python nếu làm Python. So số dòng với bản stack.
3. Sửa cây (thêm món) trong lúc đang duyệt. Quyết định hành vi: ném lỗi hay bỏ qua. Viết test.

✅ Tiêu chí hoàn thành

• Test số phần tử duyệt được pass.
• 3 bộ lọc dùng chung 1 hàm duyệt.
• In được 2 thứ tự DFS và BFS trên cùng cây.
• Giải thích được vì sao iterator ngoài cho phép lọc còn print() đệ quy thì không.

❓ Câu hỏi ôn tập

• Vì sao cây Composite cần Iterator ngoài?
• Ngăn xếp giúp đi sâu dần thế nào?
• Phục vụ lọc chay mà không biết cây ra sao?
• Duyệt trong và ngoài khác nhau ở điểm nào?

🌕 Bạn đã hoàn thành ngày 68. Làm hết bài tập phía trên rồi sang ngày tiếp theo.