Bạn đã từng nghe nhiều về Rust, nhưng chưa thấy một bài viết nào áp dụng Rust một cách toàn diện. Vì vậy, trong bài viết này, chúng ta sẽ bắt đầu bằng việc thực hiện thuật toán duyệt cây nhị phân.
Kiến thức cơ bản
Cây nhị phân là một cấu trúc dữ liệu dạng cây, mỗi node có từ một đến hai node con. Các tên gọi trong một node của cây nhị phân:
- Root: node hiện tại đang xét.
- Left: node con bên trái của node đang xét.
- Right: node con bên phải của node đang xét.
Duyệt cây nhị phân là một trong các thuật toán cơ bản khi làm việc với kiểu dữ liệu này. Có 2 cách để duyệt một cây nhị phân:
- Duyệt sâu (depth first traversal): duyệt theo thứ tự Left -> Root -> Right.
- Duyệt rộng (breadth first traversal): duyệt từng level của cây và duyệt hết tất cả các node ở từng level.
Đối với duyệt sâu, chúng ta có 3 phương pháp khác nhau, phân loại dựa theo thứ tự thăm các node con của cây:
- In-order: duyệt theo thứ tự Left -> Root -> Right.
- Pre-order: duyệt theo thứ tự Root -> Left -> Right.
- Post-order: duyệt theo thứ tự Left -> Right -> Root.
Implementation
Chúng ta sẽ implement kiểu dữ liệu binary tree trong Rust và sau đó thực hiện thuật toán duyệt cây cho kiểu dữ liệu này.
Trong quá trình implement, mình sẽ chỉ ra một số lỗi mà người mới học Rust thường gặp phải, và Rust compiler sẽ giúp chúng ta nhận ra và giải quyết các lỗi đó rất hiệu quả.
Để bắt đầu, ta cần khỏi tạo dự án Rust và tạo file binary_tree.rs nằm trong thư mục ~/code/playground/. Bạn có thể biên dịch và chạy chương trình bằng lệnh rustc binary_tree.rs.
Sau đó, chúng ta sẽ khai báo cấu trúc dữ liệu của một node trong binary tree. Đối với mỗi node, chúng ta sẽ khai báo 3 trường Value, Left và Right. Value là giá trị của node, Left là node con bên trái và Right là node con bên phải.
Cần lưu ý rằng khi khai báo recursive struct trong Rust, ta cần sử dụng Box để giải quyết vấn đề kích thước vô hạn của recursive struct. Đồng thời, cũng cần thêm attribute #[allow(dead_code)] để tránh lỗi khi compile.
Tiếp theo, chúng ta sẽ tạo binary tree từ các node đã khai báo. Bằng cách sử dụng macro node!, ta có thể tạo node mới một cách dễ dàng.
Cuối cùng, chúng ta sẽ implement thuật toán duyệt cây sử dụng phương pháp in-order. Chúng ta sẽ tạo một hàm traversal() để duyệt cây và trả về một chuỗi chứa các giá trị của các node theo thứ tự in-order.
Sau khi đã implement thành công các phần trên, chúng ta có thể gọi hàm traversal() để in ra nội dung của cây.
Đây là code đầy đủ của chúng ta:
struct Node {
value: i32,
left: Option>,
right: Option>,
}
impl Node {
fn traversal(&self) -> String {
let mut result = String::new();
if let Some(node) = &self.left {
result.push_str(&node.traversal());
}
result.push_str(&self.value.to_string());
result.push_str(", ");
if let Some(node) = &self.right {
result.push_str(&node.traversal());
}
result
}
}
fn main() {
let tree = Node {
value: 1,
left: Some(Box::new(Node {
value: 2,
left: Some(Box::new(Node {
value: 5,
left: None,
right: None,
})),
right: Some(Box::new(Node {
value: 6,
left: Some(Box::new(Node {
value: 11,
left: None,
right: None,
})),
right: None,
})),
})),
right: Some(Box::new(Node {
value: 7,
left: None,
right: Some(Box::new(Node {
value: 8,
left: Some(Box::new(Node {
value: 9,
left: None,
right: None,
})),
right: None,
})),
})),
};
println!("In-order traversal: {}", tree.traversal());
} Sau khi chạy chương trình, kết quả sẽ là: 5, 11, 6, 2, 1, 7, 9, 8.
Cảm ơn bạn đã đọc bài viết này và hy vọng bạn đã học được nhiều điều thú vị khi sử dụng Rust. Bạn có thể thử áp dụng thuật toán duyệt cây với các cách duyệt khác nhau như pre-order, post-order, hoặc thử tìm hiểu thêm về thuật toán duyệt cây theo phạm vi (BFS).
Nếu bạn muốn tìm hiểu thêm về Rust, hãy tham khảo các tài liệu tham khảo dưới đây.
Tham khảo:
Về chúng tôi: DVMS Co.,Ltd là một công ty chuyên tư vấn và triển khai các giải pháp phần mềm, mạng xã hội, ứng dụng di động và nhiều lĩnh vực công nghệ thông tin khác. Chúng tôi có kinh nghiệm lâu năm và cam kết mang đến những giải pháp chất lượng cho khách hàng.
Tại sao chọn DVMS?
- DVMS có đội ngũ chuyên gia có kiến thức sâu rộng về nhiều công nghệ phần mềm, mạng và viễn thông.
- DVMS có kinh nghiệm triển khai các hệ thống trên các nền tảng điện toán đám mây nổi tiếng như Google, Amazon, Microsoft.
- DVMS có kinh nghiệm thực tế tư vấn, xây dựng và triển khai các giải pháp phần mềm cho khách hàng trong và ngoài nước.
Mọi chi tiết vui lòng xem hồ sơ năng lực của DVMS hoặc gửi yêu cầu tư vấn và báo giá.