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

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

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

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

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

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

ตัวอย่าง

#include<iostream>
#include <stack>
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)
   return;
   stack<node *> nodeStack;
   nodeStack.push(root);
   while (nodeStack.empty() == false) {
      struct node *temp_node = nodeStack.top();
      cout<< temp_node->data <<" ";
      nodeStack.pop();
      if (temp_node→right)
      nodeStack.push(temp_node->right);
      if (temp_node→left)
      nodeStack.push(temp_node->left);
   }
}
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, 5);
   insertNode(root, 8);
   insertNode(root, 3);
   insertNode(root, 2);
   insertNode(root, 6);
   insertNode(root, 9);
   insertNode(root, 4);
   cout<<"Pre-Order traversal of the Binary Search Tree is: ";
   preorder(root);
}

ผลลัพธ์

Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 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() ใช้สแต็คเพื่อพิมพ์องค์ประกอบของต้นไม้ในการสั่งซื้อล่วงหน้า ขั้นแรกให้ใส่โหนดรูทลงในสแต็ก วง while เริ่มทำงานจนกว่า stack จะไม่ว่าง ขั้นแรก ข้อมูลในองค์ประกอบ topnode ของสแต็กจะแสดงขึ้น จากนั้นโหนดจะถูกเปิด จากนั้นโหนดด้านขวาและด้านซ้ายของโหนดด้านบนจะถูกผลักเข้าไปในสแต็ก

ฟังก์ชันนี้แสดงให้เห็นโดยใช้ข้อมูลโค้ดต่อไปนี้

void preorder(struct node *root) {
   if (root == NULL)
   return;
   stack<node *> nodeStack;
   nodeStack.push(root);
   while (nodeStack.empty() == false) {
      struct node *temp_node = nodeStack.top();
      cout<< temp_node->data <<" ";
      nodeStack.pop();
      if (temp_node→right)
      nodeStack.push(temp_node→right);
      if (temp_node→left)
      nodeStack.push(temp_node→left);
   }
}

ฟังก์ชัน 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, 5);
insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 2);
insertNode(root, 6);
insertNode(root, 9);
insertNode(root, 4);

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

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