C++ প্রোগ্রাম: টার্নারি ট্রি ইমপ্লিমেন্টেশন এবং ট্রাভার্সাল

টার্নারি ট্রি একটি ট্রি ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বোচ্চ তিনটি চাইল্ড নোড থাকে, সাধারণত "left", "mid" এবং "right" হিসেবে প্রকাশ করা হয়। এই ট্রিতে, চাইল্ড সহ নোডগুলো প্যারেন্ট নোড, এবং চাইল্ড নোডগুলো তাদের প্যারেন্টের রেফারেন্স ধারণ করতে পারে। এটি টার্নারি ট্রি ইমপ্লিমেন্টেশন এবং ট্রাভার্সালের একটি 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, int depth)
    if (root) traverseTTtil(root->l, buffer, depth)
    buffer[depth] = root->d
    if (root->EndOfString) buffer[depth+1] = '\0', print 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