C++ प्रोग्राम एक बाइनरी सर्च ट्री में डिक्शनरी ऑपरेशन करने के लिए

बाइनरी सर्च ट्री एक सॉर्ट किया गया बाइनरी ट्री है जिसमें सभी नोड्स में निम्नलिखित दो गुण होते हैं-

किसी नोड के दाएँ उप-वृक्ष की कुंजी उसके पैरेंट नोड की कुंजी से बड़ी होती है।

किसी नोड के बाएँ उप-वृक्ष की कुंजी उसके पैरेंट नोड की कुंजी से कम या उसके बराबर होती है।

प्रत्येक नोड में दो से अधिक बच्चे नहीं होने चाहिए।

यह एक बाइनरी सर्च ट्री में डिक्शनरी ऑपरेशन करने के लिए C++ प्रोग्राम है।

एल्गोरिदम

सम्मिलित करने के लिए:

Begin
   Declare function insert(int k)
      in = int(k mod max)
      p[in] = (n_type*) malloc(sizeof(n_type))
      p[in]->d = k
      if (r[in] == NULL) then
         r[in] = p[in]
         r[in]->n = NULL
         t[in] = p[in]
      else
         t[in] = r[in]
         while (t[in]->n != NULL)
            t[in] = t[in]->n
         t[in]->n= p[in]
End.

खोज के लिए एक मान:

Begin
   Declare function search(int k)
      int flag = 0
      in= int(k mod max)
      t[in] = r[in]
      while (t[in] != NULL) do
         if (t[in]->d== k) then
            Print “Search key is found”.
            flag = 1
            break
         else
            t[in] = t[in]->n
      if (flag == 0)
         Print “search key not found”.
End.

हटाने के लिए:

Begin
   Declare function delete_element(int k)
      in = int(k mod max)
      t[in] = r[in]
      while (t[in]->d!= k and t[in] != NULL)
         p[in] = t[in]
         t[in] = t[in]->n
      p[in]->n = t[in]->n
      Print the deleted element
      t[in]->d = -1
      t[in] = NULL
      free(t[in])
End

उदाहरण

#include<iostream>
#include<stdlib.h>
using namespace std;
# define max 20
typedef struct dictionary {
   int d;
   struct dictionary *n;
} n_type;
n_type *p[max], *r[max], *t[max];
class Dict {
   public:
      int in;
      Dict();
      void insert(int);
      void search(int);
      void delete_element(int);
};
int main(int argc, char **argv) {
   int v, choice, n, num;
   char c;
   Dict d;
   do {
      cout << "\n1.Create";
      cout << "\n2.Search for a value";
      cout<<"\n3.Delete a value";
      cout << "\nEnter your choice:";
      cin >> choice;
      switch (choice) {
         case 1:
            cout << "\nEnter the number of elements to be inserted:";
            cin >> n;
            cout << "\nEnter the elements to be inserted:";
            for (int i = 0; i < n; i++) {
               cin >> num;
               d.insert(num);
            }
         break;
         case 2:
            cout << "\nEnter the element to be searched:";
            cin >> n;
            d.search(n);
         case 3:
            cout << "\nEnter the element to be deleted:";
            cin >> n;
            d.delete_element(n);
         break;
         default:
            cout << "\nInvalid choice....";
            break;
      }
      cout << "\nEnter y to continue......";
      cin >> c;
   }
   while (c == 'y');
}
Dict::Dict() {
   in = -1;
   for (int i = 0; i < max; i++) {
      r[i] = NULL;
      p[i] = NULL;
      t[i] = NULL;
   }
}
void Dict::insert(int k) {
   in = int(k % max);
   p[in] = (n_type*) malloc(sizeof(n_type));
   p[in]->d = k;
   if (r[in] == NULL) {
      r[in] = p[in];
      r[in]->n = NULL;
      t[in] = p[in];
   } else {
      t[in] = r[in];
      while (t[in]->n != NULL)
      t[in] = t[in]->n;
      t[in]->n= p[in];
   }
}
void Dict::search(int k) {
   int flag = 0;
   in= int(k % max);
   t[in] = r[in];
   while (t[in] != NULL) {
      if (t[in]->d== k) {
         cout << "\nSearch key is found!!";
         flag = 1;
         break;
      } else
         t[in] = t[in]->n;
   }
   if (flag == 0)
      cout << "\nsearch key not found.......";
}
void Dict::delete_element(int k) {
   in = int(k % max);
   t[in] = r[in];
   while (t[in]->d!= k && t[in] != NULL) {
      p[in] = t[in];
      t[in] = t[in]->n;
   }
   p[in]->n = t[in]->n;
   cout << "\n" << t[in]->d << " has been deleted.";
   t[in]->d = -1;
   t[in] = NULL;
   free(t[in]);
}

आउटपुट

1.Create
2.Search for a value
3.Delete a value
Enter your choice:1
Enter the number of elements to be inserted:3
Enter the elements to be inserted:111 222 3333
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:2
Enter the element to be searched:111
Search key is found!!
Enter the element to be deleted:222
222 has been deleted.
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:222
Invalid choice....
Enter y to continue......y
1.Create
2.Search for a value
3.Delete a value
Enter your choice:2
Enter the element to be searched:222
search key not found.......
Enter the element to be deleted:0