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

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

ตัวอย่างของ Inorder traversal ของไบนารีทรีมีดังนี้

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

Inorder Traversal คือ:1 4 5 6 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 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;
}

ผลลัพธ์

In-Order traversal of the Binary Search Tree is: 1 2 3 4 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;
}

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

void inorder(struct node *root) {
   if (root != NULL) {
      inorder(root->left);
      cout<<root->data<<" ";
      inorder(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);

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

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