Chương trình C++ triển khai cây ternary (ba nhánh)

Cây ternary (ba nhánh) là cấu trúc dữ liệu cây mà mỗi nút có tối đa ba nút con, thường biểu diễn là "left", "mid" và "right". Trong cây này, nút có con là nút cha, và nút con có thể chứa tham chiếu đến cha. Đây là chương trình C++ triển khai cây ternary và duyệt cây.

Thuật toán

Begin
    Khai báo hàm 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.

Duyệt cây:

Begin
    Khai báo hàm 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'
                in giá trị buffer.
            traverseTTtil(root->eq, buffer, depth + 1);
            traverseTTtil(root->r, buffer, depth);
End.

Ví dụ

#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);
}

Kết quả

Following is traversal of ternary tree
bat hat mat rat