• Home
  • /
  • Blog
  • /
  • बाइनरी सर्च ट्रीज़ – 3 विभिन्न बाइनरी ट्री ट्रैवर्सल्स बच्चों को जानना चाहिए

बाइनरी सर्च ट्रीज़ – 3 विभिन्न बाइनरी ट्री ट्रैवर्सल्स बच्चों को जानना चाहिए

दिसम्बर 28, 2020

binary search trees

This post is also available in: English (English) العربية (Arabic)

बाइनरी ट्री एक नॉन-लीनियर डेटा स्ट्रक्चर होता है। इसलिए एक बाइनरी ट्री को एक से अधिक तरीकों से ट्रैवर्स किया जा सकता है। आइए विभिन्न बाइनरी ट्री ट्रैवर्सल्स पर चर्चा करें, जिन्हें बच्चों को जानना चाहिए।

बाइनरी सर्च ट्री ट्रैवर्सल

एक बाइनरी ट्री को तीन विभिन्न प्रकार से ट्रेस किया जा सकता है और ये हैं

  • प्रीऑर्डर (Preorder)
  • इनआर्डर (Inorder)
  • पोस्टआर्डर (Postorder)

प्रीआर्डर ट्रेवेर्सल

इस विधि में पहले नोड के सबसे पहले रूट का दौरा किया जाता है, फिर लेफ्ट सबट्री (या लेफ्ट नोड), और अंत में राइट सबट्री (या राइट नोड) का दौरा किया जाता है। सभी नोड्स का दौरा किए जाने तक प्रक्रिया को दोहराया जाता है। प्रक्रिया को समझने के लिए, निम्नलिखित बाइनरी ट्री को उदाहरण के लिए लेते हैं।

बाइनरी सर्च ट्री
बाइनरी ट्री

इस बाइनरी ट्री में, रूट में मान 1 है। दौरा किया जाने वाला पहला नोड 1 है। इसके बाद बायां सबट्री है। बायां सबट्री है –

बाइनरी सर्च ट्री
बायां सबट्री

एक प्रीऑर्डर विधि के अनुसार, सबसे पहले, रूट (मान 2) का दौरा किया जाता है, फिर बाएं नोड (मान 4) का दौरा किया जाता है और फिर दाएं नोड (मान 3) का दौरा किया जाता है। इसके साथ, बाएं सबट्री के सभी नोड्स का दौरा संपन्न हो जाता है।

उसके बाद दाएं सबट्री का दौरा किया जाता है। दायां सुबट्री है –

बाइनरी सर्च ट्री
दायां सबट्री –

इस सबट्री में, रूट नोड (मान 3) का दौरा किया जाता है, उसके बाद बाएं नोड (मान 6) और अंत में दायां नोड (मान 7) का।

प्रीऑर्डर ट्रैवर्सल विधि का उपयोग करके देखे गए नोड्स का क्रम 1, 2, 4, 5, 3, 6 और 7 है।

प्रीआर्डर ट्रैवर्सल के लिए एल्गोरिथ्म

जब तक सभी नोड्स ट्रैवर्स नहीं की जाती:

Step 1: Visit the root node.

Step 2: Recursively traverse the left subtree.

Step 3: Recursively traverse the right subtree.

C ++ में प्रीआर्डर ट्रेवेर्सल के लिए कोड

struct node {
   int data;
   struct node *left;
   struct node *right;
};
void preorder(struct node *root) {
   if (root != NULL) {
      cout<<root->data<<" ";
      preorder(root->left);
      preorder(root->right);
   }
}
int main() {
   struct node *root = NULL;
   cout<<"Pre-Order traversal of the Binary Search Tree is: ";
   preorder(root);
   return 0;
}

इनआर्डर ट्रैवर्सल

इस विधि में सबसे पहले बाएं सबट्री (या बाएं नोड) का दौरा किया जाता है, फिर रूट, और अंत में दाएं सबट्री (या दायां नोड)। सभी नोड्स का दौरा किए जाने तक प्रक्रिया को दोहराया जाता है। प्रक्रिया को समझने के लिए, निम्नलिखित बाइनरी ट्री को उदाहरण के लिए लेते हैं।

बाइनरी सर्च ट्री
बाइनरी ट्री

इस बाइनरी ट्री में, बायां सबट्री है –

बाइनरी सर्च ट्री
बायां सबट्री

इनआर्डर विधि के अनुसार, सबसे पहले, बाएं (मान 4) का दौरा किया जाता है, फिर रूट (मान 2) का दौरा किया जाता है और फिर दाएं नोड (मान 5) का दौरा किया जाता है। इसके साथ, बाएं सबट्री के सभी नोड्स का दौरा संपन्न हो जाता है।

इसके बाद, बाइनरी ट्री के रूट (मान 1) का दौरा किया जाता है।

उसके बाद दाएं सबट्री का दौरा किया जाता है। दायां सुबट्री है –

बाइनरी सर्च ट्री
दायां सबट्री –

इस सबट्री में, बाएं नोड (मान 6) का दौरा किया जाता है, उसके बाद रूट नोड (मान 3) और अंत में दाएं नोड (मान 7) का दौरा किया जाता है।

इनआर्डर ट्रेवेर्सल विधि का उपयोग करके देखे गए नोड्स का क्रम 4, 2, 5, 1, 6, 3, और 7 है।

इनआर्डर ट्रैवर्सल के लिए एल्गोरिदम

जब तक सभी नोड्स ट्रैवर्स नहीं की जाती:

Step 1: Recursively traverse the left subtree.

Step 2: Visit the root node.

Step 3: Recursively traverse the right subtree.

C ++ में इनआर्डर ट्रेवेर्सल के लिए कोड

struct node {
   int data;
   struct node *left;
   struct node *right;
};
void inorder(struct node *root) {
   if (root != NULL) {
      inorder(root->left);
      cout<<root->data<<" ";
      inorder(root->right);
   }
}
int main() {
   struct node *root = NULL;
   cout<<"In-Order traversal of the Binary Search Tree is: ";
   inorder(root);
   return 0;
}

पोस्टऑर्डर ट्रैवर्सल

इस विधि में सबसे पहले बाएं सबट्री (या बाएं नोड) का दौरा किया जाता है, फिर दाएं सबट्री (या दाएं नोड), और अंत में रूट का दौरा किया जाता है। सभी नोड्स का दौरा किए जाने तक प्रक्रिया को दोहराया जाता है। प्रक्रिया को समझने के लिए, निम्नलिखित बाइनरी ट्री को उदाहरण के लिए लेते हैं।

बाइनरी सर्च ट्री
बाइनरी ट्री

इस बाइनरी ट्री में, बायां सबट्री है –

बाइनरी सर्च ट्री
बायां सबट्री

फिर से एक पोस्टऑर्डर विधि के अनुसार, सबसे पहले, बाएं (मान 4) का दौरा किया जाता है, फिर दाएं नोड (मान 5) का दौरा किया जाता है और फिर रूट (मान 2) का दौरा किया जाता है। इसके साथ, बाएं सबट्री के सभी नोड्स का दौरा संपन्न हो जाता है।

इसके बाद, दाएं सबट्री का दौरा किया जाता है। दायां सुबट्री है –

बाइनरी सर्च ट्री
दायां सबट्री –

इस सबट्री में, बाएं नोड (मान 6) का पहले दौरा किया जाता है, उसके बाद दाएं नोड (मान 7) और अंत में रूट नोड (मान 3) का।

और अंत में, बाइनरी ट्री के रूट (मान 1) का दौरा किया जाता है।

पोस्टऑर्डर ट्रेवेर्सल विधि का उपयोग करके देखे गए नोड्स का क्रम 4, 5, 2, 6, 7, 3 और 1 है।

पोस्टऑर्डर ट्रैवर्सल के लिए एल्गोरिदम

जब तक सभी नोड्स ट्रैवर्स नहीं की जाती:

Step 1: Recursively traverse the left subtree.

Step 2: Recursively traverse the right subtree.

Step 3: Visit the root node.

C ++ में पोस्टआर्डर ट्रेवेर्सल के लिए कोड

struct node {
   int data;
   struct node *left;
   struct node *right;
};
void postorder(struct node *root) {
   if (root != NULL) {
      postorder(root->left);
      postorder(root->right);
      cout<<root->data<<" ";
   }
}
int main() {
   struct node *root = NULL;
   cout<<"Post-Order traversal of the Binary Search Tree is: ";
   postorder(root);
   return 0;
}

बाइनरी सर्च ट्री क्या होता है?

बाइनरी सर्च ट्री (BST) एक बाइनरी ट्री है जिसमें सभी नोड्स निम्नलिखित गुणों का पालन करते हैं:

  • बाईं सबट्री की कुंजी का मान उसके रूट नोड की कुंजी के मान से कम है।
  • दायीं सबट्री की कुंजी का मूल्य उसके रूट नोड की कुंजी के मान से अधिक है।
बाइनरी सर्च ट्री
बाइनरी सर्च ट्री

उपरोक्त बाइनरी ट्री में, यदि आप कोई भी मान लेते हैं, तो इसके बाएं नोड का मान कम है और दाएं नोड का अधिक है।

बाइनरी सर्च ट्री का उपयोग कहाँ किया जाता है?

डेटा को सॉर्ट (क्रम में) करने के लिए बाइनरी सर्च ट्री का उपयोग किया जाता है। जब एक बाइनरी सर्च ट्री को एक इनआर्डर विधि से ट्रेस किया जाता है, तो विज़िट किए गए एलिमेंट्स आरोही क्रम में होते हैं। अब हम उपरोक्त बाइनरी ट्री को इनआर्डर विधि से ट्रैवर्स करते हैं।

सबसे पहले बाएं सबट्री का दौरा किया जाता है। बायां सबट्री है –

बाइनरी सर्च ट्री
बायां सबट्री

सबसे पहले बाएं नोड (मान 1) का दौरा किया जाता है। उसके बाद रूट (मान 3) का दौरा किया है। उसके बाद, दाएं सबट्री का दौरा किया जाता है।

बाइनरी सर्च ट्री
बायां सबट्री

इस सबट्री में पहले बाएं नोड (मान 4) का दौरा किया जाता है, उसके बाद रूट (मान 6), और दाएं नोड (मान 7) का दौरा किया जाता है।

अब, मूल बाइनरी ट्री के सभी बायीं नोड्स का दौरा हो चुका है। अब रूट नोड (मान 8) का दौरा किया जाता है।

रूट नोड पर जाने के बाद, दाएं सबट्री का दौरा किया जाता है।

बाइनरी सर्च ट्री
दायां सबट्री –

इस सबट्री में, चूंकि कोई बायीं नोड नहीं है, इसलिए, रूट नोड (मान 10) का दौरा किया जाता है, और फिर दाएं सबट्री (केवल 2 नोड्स वाले) का।

अंत में, अंतिम सबट्री के बाएं नोड (मान 13) का दौरा किया जाता है, और इसके बाद मूल (मान 14) का। (इस सबट्री में कोई दायां सबट्री या नोड नहीं है)।

ट्रैवर्सल का परिणाम 1, 3, 4, 6, 7, 8, 10, 13 और 14 है जो कि बढ़ते क्रम में हैं।

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}
>