Nhằm giúp ace nâng cao kỹ năng, kiến thức lập trình, dễ dàng ghi nhớ và hiểu sâu hơn khi đã học lý thuyết về Queue tại series tự học cấu trúc dữ liệu và giải thuật của cafedev. Sau đây là các bài tập có full lời giải và hướng dẫn giải cực chi tiết cho ace trên nhiều ngôn ngữ lập trình khác nhau.
Bài 1: Tính chiều cao của cây nhị phân bằng Đệ quy or vòng lặp
Viết một thuật toán hiệu quả để tính toán chiều cao của cây nhị phân. Chiều cao hoặc chiều sâu của cây là số cạnh hoặc nút trên đường đi dài nhất từ nút gốc đến nút lá.
Chương trình sẽ xem xét số lượng nút trong đường dẫn dài nhất. Ví dụ, chiều cao của cây trống là 0 và chiều cao của cây chỉ có một nút là 1.
Gợi ý: Ý tưởng là đi ngang qua cây theo thứ tự sau và tính chiều cao của cây con bên trái và bên phải. Chiều cao của cây con bắt nguồn từ bất kỳ nút nào sẽ bằng chiều cao tối đa của cây con bên trái và bên phải cộng với một. Chúng ta áp dụng một cách đệ quy thuộc tính này cho tất cả các nút cây theo cách từ dưới lên (theo thứ tự sau) và trả về chiều cao tối đa của cây con có gốc tại nút đó.
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải bằng vòng lặp
Bài giải bằng đệ quy
Bài 2: In các nút góc của mọi cấp trong cây nhị phân
Cho một cây nhị phân, in các nút góc của mọi cấp trong đó.
Ví dụ:
Output:
6
3 8
4 2
1 3
Gợi ý: Ý tưởng rất đơn giản. Chúng ta sửa đổi trình tự mức độ của cây nhị phân để duy trì mức độ của mỗi nút. Sau đó, trong khi thực hiện duyệt thứ tự mức, nếu nút hiện tại là nút đầu tiên hoặc nút cuối cùng trong mức hiện tại, chúng ta chỉ cần in nó.
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải
Bài 3: Tạo số nhị phân từ 1 đến N bằng cách sử dụng Hàng đợi
Cho một số dương N, tạo hiệu quả các số nhị phân từ 1 đến N bằng cách sử dụng cấu trúc dữ liệu hàng đợi và trong thời gian tuyến tính.
Ví dụ: Với N = 10 và binary như sau:
1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải
Output: 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
