C++ प्रोग्राम: टर्नरी ट्री कार्यान्वित करना

एक टर्नरी ट्री, एक ट्री डेटा संरचना है जिसमें प्रत्येक नोड में अधिकतम तीन चाइल्ड नोड्स होते हैं, जिन्हें आमतौर पर "लेफ्ट", "मिड" और "राइट" के रूप में दर्शाया जाता है। इस ट्री में, चाइल्ड वाले नोड्स पैरेंट नोड्स होते हैं, और चाइल्ड नोड्स में उनके पैरेंट्स के संदर्भ हो सकते हैं। यह टर्नरी ट्री को लागू करने और ट्री के ट्रैवर्सल के लिए एक C++ प्रोग्राम है।

एल्गोरिदम

Begin
    फंक्शन insert(struct nod** root, char *w) घोषित करें
        if (!(*root)) तो
            *root = newnod(*w);
        if ((*w) < (*root)->d) तो
            insert(&( (*root)->l ), w);
        else if ((*w) > (*root)->d) तो
            insert(&( (*root)->r ), w);
        else if (*(w+1))
            insert(&( (*root)->eq ), w+1);
        else
            (*root)->EndOfString = 1;
End.

ट्री के ट्रैवर्सल के लिए:

Begin
    फंक्शन traverseTTtil(struct nod* root, char* buffer, depth) घोषित करें
        if (root) तो
            traverseTTtil(root->l, buffer, depth)
            buffer[depth] = root->d
            if (root->EndOfString) तो
                buffer[depth+1] = '\0'
                buffer का मान प्रिंट करें।
            traverseTTtil(root->eq, buffer, depth + 1);
            traverseTTtil(root->r, buffer, depth);
End.

उदाहरण

#include<stdlib.h>
#include<iostream>
using namespace std;

struct nod {
    char d;
    unsigned EndOfString: 1;
    struct nod *l, *eq, *r;
}*t = NULL;

struct nod* newnod(char d) {
    t = new nod;
    t->d = d;
    t->EndOfString = 0;
    t->l = t->eq = t->r = NULL;
    return t;
}

void insert(struct nod** root, char *w) {
    if (!(*root))
        *root = newnod(*w);
    if ((*w) < (*root)->d)
        insert(&( (*root)->l ), w);
    else if ((*w) > (*root)->d)
        insert(&( (*root)->r ), w);
    else {
        if (*(w+1))
            insert(&( (*root)->eq ), w+1);
        else
            (*root)->EndOfString = 1;
    }
}

void traverseTTtil(struct nod* root, char* buffer, int depth) {
    if (root) {
        traverseTTtil(root->l, buffer, depth);
        buffer[depth] = root->d;
        if (root->EndOfString) {
            buffer[depth+1] = '\0';
            cout<<buffer<<endl;
        }
        traverseTTtil(root->eq, buffer, depth + 1);
        traverseTTtil(root->r, buffer, depth);
    }
}

void traverseTT(struct nod* root) {
    char buffer[50];
    traverseTTtil(root, buffer, 0);
}

int main() {
    struct nod *root = NULL;
    insert(&root, "mat");
    insert(&root, "bat");
    insert(&root, "hat");
    insert(&root, "rat");
    cout<<"Following is traversal of ternary tree\n";
    traverseTT(root);
}

आउटपुट

Following is traversal of ternary tree
bat
hat
mat
rat