Chương trình C ++ để thực hiện truyền tải đệ quy Inorder 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. Quá trình duyệt inorder 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, Gốc, Phải).

Ví dụ về việc duyệt Inorder của cây nhị phân như sau.

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

Inorder Traversal là:1 4 5 6 8

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

Đầu ra

In-Order traversal of the Binary Search Tree is: 1 2 3 4 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 inorder () 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 trong inorder. Nó là một hàm đệ quy. Nó được chứng minh bằng cách sử dụng đoạn mã sau.

void inorder(struct node *root) {
   if (root != NULL) {
      inorder(root->left);
      cout<<root->data<<" ";
      inorder(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 inorder () đượ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 inorder. Điều này được đưa ra bên dưới.

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