Duyệt cây là một dạng duyệt đồ thị. Nó liên quan đến việc kiểm tra hoặc in mỗi nút trong cây chính xác một lần. Việc duyệt qua thứ tự bưu điện của cây tìm kiếm nhị phân liên quan đến việc truy cập từng nút trong cây theo thứ tự (Trái, Phải, Gốc).
Một ví dụ về duyệt thứ tự sau của cây nhị phân như sau.
Một cây nhị phân được đưa ra như sau.
Đường truyền đơn hàng sau là:1 5 4 8 6
Chương trình thực hiện duyệt đệ quy thứ tự sau được đưa ra như sau.
Ví dụ
#include<iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"Post-Order traversal of the Binary Search Tree is: ";
postorder(root);
return 0;
} Đầu ra
Post-Order traversal of the Binary Search Tree is: 1 3 2 9 5 4
Trong chương trình trên, nút cấu trúc tạo ra nút của cây. Cấu trúc này là một cấu trúc tự tham chiếu vì nó chứa các con trỏ kiểu nút cấu trúc. Cấu trúc này được hiển thị như sau.
nút cấu trúcstruct node {
int data;
struct node *left;
struct node *right;
}; Hàm createNode () tạo một nút tạm thời và cấp phát bộ nhớ cho nó bằng cách sử dụng malloc. Giá trị dữ liệu val được lưu trữ trong dữ liệu tạm thời. NULL được lưu trữ trong các con trỏ trái và phải của nhiệt độ. Điều này được chứng minh bằng đoạn mã sau.
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
} Hàm postorder () lấy gốc của cây nhị phân làm đối số và in các phần tử của cây theo thứ tự đăng. Nó là một hàm đệ quy. Nó được chứng minh bằng cách sử dụng đoạn mã sau.
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
} Hàm insertNode () chèn giá trị cần thiết trong cây nhị phân vào đúng vị trí của nó. Nếu nút là NULL, thì createNode được gọi. Nếu không, vị trí chính xác của nút được tìm thấy trong cây. Điều này có thể được quan sát trong đoạn mã sau.
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
} Trong hàm main (), nút gốc đầu tiên được định nghĩa là NULL. Sau đó, tất cả các nút với các giá trị cần thiết được chèn vào cây tìm kiếm nhị phân. Điều này được hiển thị bên dưới.
struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
Cuối cùng, hàm postorder () được gọi bằng cách sử dụng nút gốc của cây và tất cả các giá trị của cây được hiển thị trong postorder. Điều này được đưa ra bên dưới.
cout<<"Post-Order traversal of the Binary Search Tree is: "; postorder(root);