C++ Program to Implement Ternary Tree

Ternary tree เป็นโครงสร้างข้อมูลต้นไม้ที่แต่ละโหนดมี child nodes สูงสุดสามตัว มักแสดงเป็น "left", "mid" และ "right" ในต้นไม้นี้ โหนดที่มีลูกเป็น parent nodes และ child nodes อาจมี reference ไปยัง parent ของพวกเขา นี่คือ C++ Program เพื่อ Implement Ternary Tree และการ traverse ต้นไม้

Algorithm

Begin
    Declare function insert(struct nod** root, char *w)
        if (!(*root)) then
            *root = newnod(*w);
        if ((*w) < (*root)->d) then
            insert(&( (*root)->l ), w);
        else if ((*w) > (*root)->d) then
            insert(&( (*root)->r ), w);
        else if (*(w+1))
            insert(&( (*root)->eq ), w+1);
        else
            (*root)->EndOfString = 1;
End.

For Traversal of tree:

Begin
    Declare function traverseTTtil(struct nod* root, char* buffer, int depth)
        if (root) then
            traverseTTtil(root->l, buffer, depth)
            buffer[depth] = root->d
            if (root->EndOfString) then
                buffer[depth+1] = '\0'
                print the value of 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