โปรแกรม C++ เพื่อดำเนินการ Postorder Recursive Traversal ของ Binary Tree ที่ให้มา

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

ตัวอย่างของการข้ามผ่านหลังการสั่งซื้อของไบนารีทรีมีดังนี้

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

Postorder Traversal คือ:1 5 4 8 6

โปรแกรมสำหรับดำเนินการข้ามผ่านแบบเรียกซ้ำภายหลังการสั่งซื้อมีดังต่อไปนี้

ตัวอย่าง

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

ผลลัพธ์

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

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

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

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

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

ฟังก์ชัน 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);

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

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