Giải thuật và lập trình - C: BÀI TẬP

1. Trình bày các biểu thức duyệt tiền tự, trung tự, hậu tự của cây sau:

2. Duyệt cây theo mức là duyệt bắt đầu từ gốc, rồi duyệt các nút nằm trên mức 1 theo thứ tự từ trái sang phải, rồi đến các nút nằm trên mức 2 theo thứ tự từ trái sang phải...Và cứ như vậy.

  a. Hãy liệt kê các nút theo thứ tự duyệt theo mức của cây trong bài 1.

  b. Viết thủ tục duyệt cây theo mức. (Gợi ý: dùng hàng đợi)

3. Vẽ cây biểu diễn cho biểu thức ((a+b)+c*(d+e)+f)*(g+h) Trình bày biểu thức tiền tố và hậu tố của biểu thức đã cho.

4. Viết chương trình để tính giá trị của biểu thức khi cho:

  a. Biểu thức tiền tố

  b. Biểu thức hậu tố.

Ví dụ:

  - đầu vào (input): * + 6 4 5

  - thì đầu ra (output) sẽ là: 50 vì biểu thức trên là dạng tiền tố của (6+4) * 5

Tương tự:

  - đầu vào (input): 6 4 5 + *

  - thì đầu ra (output) sẽ là: 54 vì biểu thức trên là dạng hậu tố của 6 * (4+5)

  a. Hãy trình bày các duyệt: tiền tự (node-left-right), trung tự (left-node-right), hậu tự (left-right-node).

  b. Minh hoạ sự lưu trữ kế tiếp các nút cây này trong mảng.

6. Chứng minh rằng: nếu biết biểu thức duyệt tiền tự và trung tự của một cây nhị phân thì ta dựng được cây này.

Điều đó đúng nữa không? Khi biết biểu thức duyệt:

  a. Tiền tự và hậu tự

  b. Trung tự và hậu tự

7. Nêu các trường hợp mà các giải thuật trên cây TKNP:

  - Có hiệu quả nhất

  - Kém hiệu quả nhất

Từ đó nêu ra các hướng tổ chức cây TKNP để đạt được hiệu quả cao về thời gian thực hiện giải thuật.

8. a. Vẽ hình cây tìm kiếm nhị phân tạo ra từ cây rỗng bằng cách lần lượt thêm vào các khoá là các số nguyên: 54, 31, 43, 29, 65, 10, 20, 36, 78, 59.

  b. Vẽ lại hình cây tìm kiếm nhị phân ở câu a/ sau khi lần lượt xen thêm các nút 15, 45, 55.

  c. Vẽ lại hình cây tìm kiếm nhị phân ở câu a/ sau khi lần lượt xoá các nút 10, 20, 43, 65, 54.

9. Hãy dựng cây tìm kiếm nhị phân ứng với dãy khóa (thứ tự tính theo qui tắc so sánh chuỗi (string)): HAIPHONG, CANTHO, NHATRANG, DALAT, HANOI, ANGIANG, MINHHAI, HUE, SAIGON, VINHLONG. Đánh dấu đường đi trên cây khi tìm kiếm khóa DONGTHAP.

10. Cài đặt cây TKNP có khoá là chuỗi (String) với các phép toán thêm, xoá. Bổ sung thêm các thủ tục cần thiết đề có 1 chương trình hoàn chỉnh, cung cấp giao diện để người dùng có thể thêm, xoá 1 khoá và duyệt cây để kiểm tra kết quả.

11. Viết các thủ tục thêm, xoá một nút có khoá x trên cây tìm kiếm nhị phân bằng cách không đệ qui.

12. Để mở rộng khả năng xử lí các khoá trùng nhau trên cây tìm kiếm nhị phân, ta có thể tổ chức cây tìm kiếm nhị phân như sau: tại mỗi nút của cây ta tổ chức một danh sách liên kết chứa các khoá trùng nhau đó. Chẳng hạn cây được thiết lập từ dãy khoá số nguyên 10, 15, 5, 10, 20, 4, 5, 10, 15, 15, 4, 15 như sau:

Trong đó các mũi tên nằm ngang chỉ các con trỏ của danh sách liên kết.

Hãy viết khai báo cấu trúc dữ liệu và các thủ tục/hàm để cài đặt cây TKNP mở rộng như trên.