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ề Binary Tree 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: Kiểm tra xem hai cây nhị phân có giống nhau hay không dùng Đệ quy or lặp lại
Viết một thuật toán hiệu quả để kiểm tra xem hai cây nhị phân có giống nhau hay không. tức là nếu chúng có cấu trúc giống nhau thì nội dung của chúng cũng giống nhau.
Gợi ý: Ý tưởng là duyệt qua cả hai cây và so sánh giá trị tại nút gốc của chúng. Nếu giá trị khớp, chúng tôi kiểm tra đệ quy xem cây con bên trái của cây thứ nhất có giống với cây con bên trái của cây thứ hai và cây con bên phải của cây thứ nhất có trùng với cây con bên phải của cây thứ hai hay không. Nếu giá trị tại nút gốc của chúng khác nhau, cây vi phạm thuộc tính dữ liệu. Nếu tại bất kỳ thời điểm nào trong đệ quy, cây đầu tiên trống cây thứ hai không trống hoặc cây thứ hai trống cây thứ nhất không rỗng, các cây vi phạm thuộc tính cấu trúc và chúng không thể giống nhau.
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải vòng lặp
Bài giải đệ quy
Bài 2: Xóa cây nhị phân dùng Lặp lại và đệ quy
Cho một cây nhị phân, hãy viết một thuật toán hiệu quả để xóa toàn bộ cây nhị phân.
Chương trình nên khử phân bổ mọi nút đơn có trong cây, không chỉ thay đổi tham chiếu của nút gốc thành null.
Gợi ý: Ý tưởng là đi ngang cây theo thứ tự sau và xóa cây con trái và phải của một nút trước khi xóa chính nút đó. Lưu ý rằng chúng tôi không thể đi ngang qua cây theo cách đặt hàng trước hoặc đặt hàng trước vì chúng tôi không thể xóa cây gốc trước khi xóa cây con của nó
Giải bài với đệ quy
Giải bài với lặp lại
Bài 3: In chế độ xem bên trái của cây nhị phân
Cho một cây nhị phân, hãy viết một thuật toán hiệu quả để in ra chế độ xem bên trái của cây nhị phân
Ví dụ: chế độ xem bên trái của cây nhị phân bên dưới là 1, 2, 4, 7
Giải bài
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!
