Chương trình C ++ để thực hiện sắp xếp trước truyền tải đệ quy của một cây nhị phân cho trước

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 trước 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ự (Gốc, Trái, Phải).

Ví dụ về tính năng Đặt hàng trước của cây nhị phân như sau.

Một cây nhị phân được đưa ra như sau.

Đặt hàng trước Traversal là:6 4 1 5 8

Chương trình thực hiện duyệt đệ quy đặt trước đượ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 preorder(struct node *root) {
   if (root != NULL) {
      cout<<root->data<<" ";
      preorder(root->left);
      preorder(root->right);
   }
}
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<<"Pre-Order traversal of the Binary Search Tree is: ";
   preorder(root);
   return 0;
}

Đầu ra

Pre-Order traversal of the Binary Search Tree is: 4 2 1 3 5 9

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.

struct 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 preorder () 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ự trước. Nó là một hàm đệ quy. Nó được chứng minh bằng cách sử dụng đoạn mã sau.

void preorder(struct node *root) {
   if (root != NULL) {
      cout<<root-->data<<" ";
      preorder(root-->left);
      preorder(root-->right);
   }
}

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 preorder () đượ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ị theo thứ tự trước. Điều này được đưa ra bên dưới.

cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);