โปรแกรม C++ เพื่อดำเนินการสั่งจองล่วงหน้าแบบเรียกซ้ำของต้นไม้ไบนารีที่ให้มา

การข้ามต้นไม้เป็นรูปแบบหนึ่งของการข้ามผ่านกราฟ มันเกี่ยวข้องกับการตรวจสอบหรือพิมพ์แต่ละโหนดในทรีเพียงครั้งเดียว การข้ามผ่านของการสั่งซื้อล่วงหน้าของทรีการค้นหาแบบไบนารีเกี่ยวข้องกับการเยี่ยมชมแต่ละโหนดในทรีตามลำดับ (ราก ซ้าย ขวา)

ตัวอย่างการสั่งผ่านแบบพรีออร์เดอร์ของไบนารีทรีมีดังนี้

ต้นไม้ไบนารีจะได้รับดังนี้

การสั่งซื้อล่วงหน้าคือ:6 4 1 5 8

โปรแกรมสำหรับสั่งจองล่วงหน้าแบบเรียกซ้ำมีดังต่อไปนี้

ตัวอย่าง

#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;
}

ผลลัพธ์

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

ในโปรแกรมข้างต้น โครงสร้างโหนดจะสร้างโหนดของต้นไม้ โครงสร้างนี้เป็นโครงสร้างอ้างอิงตนเอง เนื่องจากมีตัวชี้ประเภทโหนดโครงสร้าง โครงสร้างนี้แสดงไว้ดังนี้

struct node {
   int data;
   struct node *left;
   struct node *right;
};

ฟังก์ชัน createNode() สร้างโหนดชั่วคราวและจัดสรรหน่วยความจำโดยใช้ malloc ค่าข้อมูลจะถูกเก็บไว้ในข้อมูลของอุณหภูมิ NULL ถูกเก็บไว้ในพอยน์เตอร์ของอุณหภูมิด้านซ้ายและขวา สิ่งนี้แสดงให้เห็นโดยข้อมูลโค้ดต่อไปนี้

struct node *createNode(int val) {
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->data = val;
   temp->left = temp->right = NULL;
   return temp;
}

ฟังก์ชั่น preorder() รับรูทของไบนารีทรีเป็นอาร์กิวเมนต์และพิมพ์องค์ประกอบของทรีในการสั่งซื้อล่วงหน้า เป็นฟังก์ชันแบบเรียกซ้ำ มันแสดงให้เห็นโดยใช้รหัสต่อไปนี้

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

ฟังก์ชัน insertNode() แทรกค่าที่ต้องการลงในไบนารีทรีในตำแหน่งที่ถูกต้อง หากโหนดเป็น NULL ระบบจะเรียก createNode มิฉะนั้น จะพบตำแหน่งที่ถูกต้องสำหรับโหนดในแผนผัง ซึ่งสังเกตได้จากข้อมูลโค้ดต่อไปนี้

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;
}

ในฟังก์ชัน main() โหนดรูทจะถูกกำหนดเป็น NULL ก่อน จากนั้นโหนดทั้งหมดที่มีค่าที่จำเป็นจะถูกแทรกลงในแผนผังการค้นหาแบบไบนารี ดังแสดงด้านล่าง

struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);

สุดท้าย ฟังก์ชัน preorder() จะถูกเรียกใช้โดยใช้โหนดรูทของทรี และค่าทรีทั้งหมดจะแสดงในการสั่งซื้อล่วงหน้า ด้านล่างนี้

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