Trong bài viết trước chúng ta đã cùng nhau tìm hiểu về Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++. Tiếp tục với chủ đề cây nhị phân, trong bài viết này, chúng ta sẽ cùng tìm hiểu về các cách duyệt cây thường dùng là duyệt tiền tố, trung tố, hậu tố.
DANH SÁCH BÀI VIẾT Tìm hiểu Cấu trúc dữ liệu Hash table trong lập trình C/C++ Cây đa phân trong lập trình C/C++ – Cấu trúc dữ liệu cây đa phân Hiểu về cấu trúc dữ liệu cây trong lập trình C/C++ Chinh phục cấu trúc dữ liệu hàng đợi lập trình C/C++ trong 5 phút Cấu trúc dữ liệu ngăn xếp trong lập trình C/C++ Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++ Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++ Cây nhị phân tìm kiếm – Tìm hiểu cây nhị phân tìm kiếm trong C/C++ Duyệt tiền tố, trung tố, hậu tố trong cây nhị phân – Lập trình C/C++
Duyệt tiền tố, trung tố, hậu tố trong cây nhị phân
Cây nhị phân là một kiểu dữ liệu phổ biến trong lập trình và được sử dụng để lưu trữ và quản lý dữ liệu theo cấu trúc cây. Một trong những thao tác quan trọng trên cây nhị phân đó là duyệt cây, bao gồm duyệt tiền tố(NLR), trung tố(LNR) và hậu tố(LRN). Trước khi đi vào chương trình minh họa cụ thể mình có ví dụ cây nhị phân như sau:
Vậy mình sẽ thực hiện duyệt cây đối với cây đồ thị này.
Duyệt tiền tố (NLR)
Duyệt tiền tố là phương pháp duyệt cây bắt đầu bằng việc ghé thăm nút gốc, sau đó là nút con bên trái và sau đó là nút con bên phải. Quá trình duyệt tiếp tục lặp lại cho đến khi duyệt hết cây.
Các bước thực hiện duyệt trung tố cây nhị phân như sau:
- Duyệt nút hiện tại.
- Duyệt cây con trái theo thứ tự hậu tố.
- Duyệt cây con phải theo thứ tự hậu tố.
Kết quả duyệt tiền tố đối với cây đồ thị trên sẽ là: 1 2 4 5 3 7 6.
Cấu trúc hàm duyệt tiền tố:
// Hàm thực hiện duyệt cây NLR(hậu tố) sử dụng đệ quy.
void NLR(Node* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
NLR(root->left);
NLR(root->right);
}
XEM THÊM: Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%
Duyệt trung tố (LNR)
Duyệt trung tố là phương pháp duyệt cây bắt đầu bằng việc ghé thăm nút con bên trái, sau đó là nút gốc và cuối cùng là nút con bên phải. Quá trình duyệt tiếp tục lặp lại cho đến khi duyệt hết cây.
Các bước thực hiện duyệt trung tố cây nhị phân như sau:
- Duyệt cây con trái theo thứ tự hậu tố.
- Duyệt nút hiện tại.
- Duyệt cây con phải theo thứ tự hậu tố.
Kết quả duyệt trung tố của cây trên là: 4 2 5 1 7 3 6.
Cấu trúc hàm duyệt trung tố:
// Hàm thực hiện duyệt cây LNR(trung tố) sử dụng đệ quy.
void LNR(Node* root) {
if (root == NULL) {
return;
}
LNR(root->left);
printf("%d ", root->data);
LNR(root->right);
}
XEM THÊM: Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
Duyệt hậu tố (LRN)
Duyệt cây nhị phân theo thứ tự hậu tố nghĩa là ta trước hết duyệt tất cả các nút con bên trái của một nút, sau đó duyệt tất cả các nút con bên phải của nút đó, và cuối cùng là duyệt nút đó chính nó.
Các bước thực hiện duyệt hậu tố cây nhị phân như sau:
- Duyệt cây con trái theo thứ tự hậu tố.
- Duyệt cây con phải theo thứ tự hậu tố.
- Duyệt nút hiện tại.
Kết quả duyệt hậu tố của cây trên là: 4 5 2 7 6 3 1
Cấu trúc hàm duyệt trung tố:
// Hàm thực hiện duyệt cây LRN (hậu tố) sử dụng đệ quy.
void LRN(Node* root) {
if (root == NULL) {
return;
}
LRN(root->left);
LRN(root->right);
cout << root->data << " ";
}
Cảm ơn bạn đã đọc hết bài viết! Chúc bạn học tốt!
[XEM TẤT CẢ BÀI VIẾT CHỦ ĐỀ C/C++ TẠI ĐÂY]
XÊM THÊM Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++ Cách tìm UCLN và BCNN Thuật toán đếm số lượng chữ số của số nguyên dương n Thuật toán tính dãy số Fibonacci Bài toán chuẩn hóa xâu ký tự Kiểm tra số chẵn lẻ trong lập trình C/C++
