सी ++ प्रोग्राम किसी दिए गए बाइनरी ट्री के प्रीऑर्डर गैर-पुनरावर्ती ट्रैवर्सल करने के लिए

ट्री ट्रैवर्सल ग्राफ ट्रैवर्सल का एक रूप है। इसमें पेड़ में प्रत्येक नोड को ठीक एक बार जांचना या प्रिंट करना शामिल है। बाइनरी सर्च ट्री के प्रीऑर्डर ट्रैवर्सल में ट्री में प्रत्येक नोड को क्रम (रूट, लेफ्ट, राइट) में जाना शामिल है।

बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल का एक उदाहरण इस प्रकार है।

एक बाइनरी ट्री इस प्रकार दिया गया है।

अग्रिम-आदेश ट्रैवर्सल है: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 () एक नोड अस्थायी बनाता है और इसे मॉलोक का उपयोग करके मेमोरी आवंटित करता है। डेटा मान वैल अस्थायी के डेटा में संग्रहीत किया जाता है। 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;
}

फ़ंक्शन प्रीऑर्डर () प्रीऑर्डर में ट्री के तत्वों को प्रिंट करने के लिए स्टैक का उपयोग करता है। सबसे पहले रूट नोड को स्टैक में डाला जाता है। थोड़ी देर का लूप शुरू होता है जो तब तक चलता है जब तक कि स्टैक खाली न हो। पहले स्टैक के टॉपनोड तत्व में डेटा प्रदर्शित किया जाता है और फिर, नोड को पॉप किया जाता है। फिर उपरोक्त नोड के दाएं और बाएं नोड्स को स्टैक में धकेल दिया जाता है।

यह फ़ंक्शन निम्न कोड स्निपेट का उपयोग करके प्रदर्शित किया जाता है।

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

फ़ंक्शन इन्सर्ट नोड () बाइनरी ट्री में आवश्यक मान को उसकी सही स्थिति में सम्मिलित करता है। यदि नोड 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;
}

मुख्य () फ़ंक्शन में, रूट नोड को पहले 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);

अंत में, फ़ंक्शन प्रीऑर्डर () को ट्री के रूट नोड का उपयोग करके कॉल किया जाता है और सभी ट्री मान प्रीऑर्डर में प्रदर्शित होते हैं। यह नीचे दिया गया है।

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