C++ Program to Implement Ternary Search Tree

«
»
This C++ Program demonstrates the implementation of Ternary Seach Tree.

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

  1. /* 
  2.  * C++ Program to Implement Ternary Seach Tree
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #define MAX 50
  7. using namespace std;
  8.  
  9. /* 
  10.  * Node Declaration
  11.  */
  12. struct Node
  13. {
  14.     char data;
  15.     unsigned isEndOfString: 1;
  16.     Node *left, *eq, *right;
  17. };
  18. /* 
  19.  * create a new ternary search tree node
  20.  */ 
  21. Node* newNode(char data)
  22. {
  23.     Node* temp = new Node;
  24.     temp->data = data;
  25.     temp->isEndOfString = 0;
  26.     temp->left = temp->eq = temp->right = NULL;
  27.     return temp;
  28. }
  29. /* 
  30.  * insert a new word in a Ternary Search Tree
  31.  */ 
  32. void insert(Node** root, char *word)
  33. {
  34.     if (!(*root))
  35.         *root = newNode(*word);
  36.     if ((*word) < (*root)->data)
  37.         insert(&((*root)->left), word);
  38.     else if ((*word) > (*root)->data)
  39.         insert(&((*root)->right), word);
  40.     else
  41.     {
  42.         if (*(word + 1))
  43.             insert(&( (*root)->eq ), word + 1);
  44.         else
  45.             (*root)->isEndOfString = 1;
  46.     }
  47. }
  48. /* 
  49.  * traverse Utility function
  50.  */  
  51. void traverseTSTUtil(Node* root, char* buffer, int depth)
  52. {
  53.     if (root)
  54.     {
  55.         traverseTSTUtil(root->left, buffer, depth);
  56.         buffer[depth] = root->data;
  57.         if (root->isEndOfString)
  58.         {
  59.             buffer[depth + 1] = '\0';
  60.             cout<<buffer<<endl;
  61.         }
  62.         traverseTSTUtil(root->eq, buffer, depth + 1);
  63.         traverseTSTUtil(root->right, buffer, depth);
  64.     }
  65. }
  66. /* 
  67.  * traverse Ternary Search Tree
  68.  */  
  69. void traverseTST(Node* root)
  70. {
  71.     char buffer[MAX];
  72.     traverseTSTUtil(root, buffer, 0);
  73. }
  74. /* 
  75.  * search a given word in Ternary Search Tree
  76.  */  
  77. int searchTST(Node *root, char *word)
  78. {
  79.     if (!root)
  80.         return 0;
  81.     if (*word < (root)->data)
  82.         return searchTST(root->left, word);
  83.     else if (*word > (root)->data)
  84.         return searchTST(root->right, word);
  85.     else
  86.     {
  87.         if (*(word + 1) == '\0')
  88.             return root->isEndOfString;
  89.         return searchTST(root->eq, word+1);
  90.     }
  91. }
  92.  
  93. /* 
  94.  * Main
  95.  */  
  96. int main()
  97. {
  98.     Node *root = NULL;
  99.     char s[100];
  100.     insert(&root, "cat");
  101.     insert(&root, "cats");
  102.     insert(&root, "up");
  103.     insert(&root, "bug");
  104.     cout<<"Following is traversal of ternary search tree\n";
  105.     traverseTST(root);
  106.     cout<<"Enter string to search: ";
  107.     cin>>s;
  108.     if (searchTST(root, s))
  109.         cout<<s<<" found in Ternary Search Tree"<<endl;
  110.     else
  111.         cout<<s<<" not found in Ternary Search Tree"<<endl;
  112.     return 0;
  113. }

$ g++ ternary_searchtree.cpp
$ a.out
 
Following is traversal of ternary search tree
bug
cat
cats
up
Enter string to search: cat
cat found in Ternary Search Tree
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

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 & technical discussions at Telegram SanfoundryClasses.