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

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

एक नोड का राइट सब-ट्री उसके पैरेंट नोड की कुंजी से अधिक कुंजी रखता है।

एक नोड का लेफ्ट सब-ट्री उसके पैरेंट नोड की कुंजी से कम या बराबर कुंजी रखता है।

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

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

एल्गोरिदम

इन्सर्ट के लिए:

Begin
    फंक्शन insert(int k) घोषित करें
        in = int(k mod 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]
End.

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

Begin
    फंक्शन 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) तो
                "Search key is found" प्रिंट करें।
                flag = 1
                break
            else
                t[in] = t[in]->n
        if (flag == 0)
            "search key not found" प्रिंट करें।
End.

डिलीट के लिए:

Begin
    फंक्शन 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
        डिलीट किया गया एलिमेंट प्रिंट करें
        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);
                break;
            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
...