Троичное дерево поиска

// C программа для демонстрации вставки троичного поискового дерева (TST), путешествия
// и поисковые операции
#include <stdio.h>
#include <stdlib.h>
#define MAX 50

  
// Узел троичного дерева поиска

struct Node

{

    char data;

    // True, если этот символ является последним символом одного из слов

    unsigned isEndOfString: 1;

    struct Node *left, *eq, *right;

};

  
// Вспомогательная функция для создания нового узла троичного поискового дерева

struct Node* newNode(char data)

{

    struct Node* temp = (struct Node*) malloc(sizeof( struct Node ));

    temp->data = data;

    temp->isEndOfString = 0;

    temp->left = temp->eq = temp->right = NULL;

    return temp;

}

  
// Функция для вставки нового слова в троичное дерево поиска

void insert(struct Node** root, char *word)

{

    // Базовый случай: дерево пусто

    if (!(*root))

        *root = newNode(*word);

    // Если текущий символ слова меньше, чем символ корня,

    // затем вставляем это слово в левое поддерево корня

    if ((*word) < (*root)->data)

        insert(&( (*root)->left ), word);

    // Если текущий символ слова больше, чем символ корня,

    // затем вставляем это слово в правое поддерево корня

    else if ((*word) > (*root)->data)

        insert(&( (*root)->right ), word);

    // Если текущий символ слова совпадает с символом root,

    else

    {

        if (*(word+1))

            insert(&( (*root)->eq ), word+1);

        // последний символ слова

        else

            (*root)->isEndOfString = 1;

    }

}

  
// Рекурсивная функция для обхода троичного дерева поиска

void traverseTSTUtil(struct Node* root, char* buffer, int depth)

{

    if (root)

    {

        // Первый переход по левому поддереву

        traverseTSTUtil(root->left, buffer, depth);

        // Сохраняем символ этого узла

        buffer[depth] = root->data;

        if (root->isEndOfString)

        {

            buffer[depth+1] = '\0';

            printf( "%s\n", buffer);

        }

        // Обход поддерева с использованием равного указателя (среднее поддерево)

        traverseTSTUtil(root->eq, buffer, depth + 1);

        // Наконец пройти через правое поддерево

        traverseTSTUtil(root->right, buffer, depth);

    }

}

  
// Основная функция для обхода троичного дерева поиска.
// Он в основном использует traverseTSTUtil ()

void traverseTST(struct Node* root)

{

    char buffer[MAX];

    traverseTSTUtil(root, buffer, 0);

}

  
// Функция для поиска заданного слова в TST

int searchTST(struct Node *root, char *word)

{

    if (!root)

        return 0;

    if (*word < (root)->data)

        return searchTST(root->left, word);

    else if (*word > (root)->data)

        return searchTST(root->right, word);

    else

    {

        if (*(word+1) == '\0')

            return root->isEndOfString;

        return searchTST(root->eq, word+1);

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Node *root = NULL;

    insert(&root, "cat");

    insert(&root, "cats");

    insert(&root, "up");

    insert(&root, "bug");

    printf("Following is traversal of ternary search tree\n");

    traverseTST(root);

    printf("\nFollowing are search results for cats, bu and cat respectively\n");

    searchTST(root, "cats")? printf("Found\n"): printf("Not Found\n");

    searchTST(root, "bu")?   printf("Found\n"): printf("Not Found\n");

    searchTST(root, "cat")?  printf("Found\n"): printf("Not Found\n");

    return 0;

}