C Program to Implement Ternary Tree

This is a C Program to implement ternary tree. A ternary search tree is a special trie data structure where the child nodes of a standard trie are ordered as a binary search tree.
Representation of ternary search trees:
Unlike trie(standard) data structure where each node contains 26 pointers for its children, each node in a ternary search tree contains only 3 pointers:
1. The left pointer points to the node whose value is less than the value in the current node.
2. The equal pointer points to the node whose value is equal to the value in the current node.
3. The right pointer points to the node whose value is greater than the value in the current node.

Here is source code of the C Program to Implement Ternary Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // C program to demonstrate Ternary Search Tree (TST) insert, travese
  2. // and search operations
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #define MAX 50
  6.  
  7. // A node of ternary search tree
  8. struct Node {
  9.     char data;
  10.  
  11.     // True if this character is last character of one of the words
  12.     unsigned isEndOfString :1;
  13.  
  14.     struct Node *left, *eq, *right;
  15. };
  16.  
  17. // A utility function to create a new ternary search tree node
  18. struct Node* newNode(char data) {
  19.     struct Node* temp = (struct Node*) malloc(sizeof(struct Node));
  20.     temp->data = data;
  21.     temp->isEndOfString = 0;
  22.     temp->left = temp->eq = temp->right = NULL;
  23.     return temp;
  24. }
  25.  
  26. // Function to insert a new word in a Ternary Search Tree
  27. void insert(struct Node** root, char *word) {
  28.     // Base Case: Tree is empty
  29.     if (!(*root))
  30.         *root = newNode(*word);
  31.  
  32.     // If current character of word is smaller than root's character,
  33.     // then insert this word in left subtree of root
  34.     if ((*word) < (*root)->data)
  35.         insert(&((*root)->left), word);
  36.  
  37.     // If current character of word is greate than root's character,
  38.     // then insert this word in right subtree of root
  39.     else if ((*word) > (*root)->data)
  40.         insert(&((*root)->right), word);
  41.  
  42.     // If current character of word is same as root's character,
  43.     else {
  44.         if (*(word + 1))
  45.             insert(&((*root)->eq), word + 1);
  46.  
  47.         // the last character of the word
  48.         else
  49.             (*root)->isEndOfString = 1;
  50.     }
  51. }
  52.  
  53. // A recursive function to traverse Ternary Search Tree
  54. void traverseTSTUtil(struct Node* root, char* buffer, int depth) {
  55.     if (root) {
  56.         // First traverse the left subtree
  57.         traverseTSTUtil(root->left, buffer, depth);
  58.  
  59.         // Store the character of this node
  60.         buffer[depth] = root->data;
  61.         if (root->isEndOfString) {
  62.             buffer[depth + 1] = '\0';
  63.             printf("%s\n", buffer);
  64.         }
  65.  
  66.         // Traverse the subtree using equal pointer (middle subtree)
  67.         traverseTSTUtil(root->eq, buffer, depth + 1);
  68.  
  69.         // Finally Traverse the right subtree
  70.         traverseTSTUtil(root->right, buffer, depth);
  71.     }
  72. }
  73.  
  74. // The main function to traverse a Ternary Search Tree.
  75. // It mainly uses traverseTSTUtil()
  76. void traverseTST(struct Node* root) {
  77.     char buffer[MAX];
  78.     traverseTSTUtil(root, buffer, 0);
  79. }
  80.  
  81. // Function to search a given word in TST
  82. int searchTST(struct Node *root, char *word) {
  83.     if (!root)
  84.         return 0;
  85.  
  86.     if (*word < (root)->data)
  87.         return searchTST(root->left, word);
  88.  
  89.     else if (*word > (root)->data)
  90.         return searchTST(root->right, word);
  91.  
  92.     else {
  93.         if (*(word + 1) == '\0')
  94.             return root->isEndOfString;
  95.  
  96.         return searchTST(root->eq, word + 1);
  97.     }
  98. }
  99.  
  100. // Driver program to test above functions
  101. int main() {
  102.     struct Node *root = NULL;
  103.  
  104.     insert(&root, "cat");
  105.     insert(&root, "cats");
  106.     insert(&root, "up");
  107.     insert(&root, "bug");
  108.  
  109.     printf("Following is traversal of ternary search tree\n");
  110.     traverseTST(root);
  111.  
  112.     printf("\nFollowing are search results for cats, bu and cat respectively\n");
  113.     searchTST(root, "cats") ? printf("Found\n") : printf("Not Found\n");
  114.     searchTST(root, "bu") ? printf("Found\n") : printf("Not Found\n");
  115.     searchTST(root, "cat") ? printf("Found\n") : printf("Not Found\n");
  116.  
  117.     return 0;
  118. }

Output:

$ gcc TernaryTree.c
$ ./a.out
 
Following is traversal of ternary search tree
bug
cat
cats
up
 
Following are search results for cats, bu and cat respectively
Found
Not Found
Found

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.