Java Program to Implement Ternary Tree

«
»
This Java program is to Implement ternary tree. In computer science, a ternary tree is a tree data structure in which each node has at most three child nodes, usually distinguished as “left”, “mid” and “right”. Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the “root” node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left, mid or right child.

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

  1. //This is a java program to implement Ternary Tree
  2. import java.util.Scanner;
  3. import java.util.ArrayList;
  4.  
  5. class TSTNode
  6. {
  7.     char    data;
  8.     boolean isEnd;
  9.     TSTNode left, middle, right;
  10.  
  11.     public TSTNode(char data)
  12.     {
  13.         this.data = data;
  14.         this.isEnd = false;
  15.         this.left = null;
  16.         this.middle = null;
  17.         this.right = null;
  18.     }
  19. }
  20.  
  21. class TernarySearchTree
  22. {
  23.     private TSTNode           root;
  24.     private ArrayList<String> al;
  25.  
  26.     public TernarySearchTree()
  27.     {
  28.         root = null;
  29.     }
  30.  
  31.     public boolean isEmpty()
  32.     {
  33.         return root == null;
  34.     }
  35.  
  36.     public void makeEmpty()
  37.     {
  38.         root = null;
  39.     }
  40.  
  41.     public void insert(String word)
  42.     {
  43.         root = insert(root, word.toCharArray(), 0);
  44.     }
  45.  
  46.     public TSTNode insert(TSTNode r, char[] word, int ptr)
  47.     {
  48.         if (r == null)
  49.             r = new TSTNode(word[ptr]);
  50.         if (word[ptr] < r.data)
  51.             r.left = insert(r.left, word, ptr);
  52.         else if (word[ptr] > r.data)
  53.             r.right = insert(r.right, word, ptr);
  54.         else
  55.         {
  56.             if (ptr + 1 < word.length)
  57.                 r.middle = insert(r.middle, word, ptr + 1);
  58.             else
  59.                 r.isEnd = true;
  60.         }
  61.         return r;
  62.     }
  63.  
  64.     public void delete(String word)
  65.     {
  66.         delete(root, word.toCharArray(), 0);
  67.     }
  68.  
  69.     private void delete(TSTNode r, char[] word, int ptr)
  70.     {
  71.         if (r == null)
  72.             return;
  73.         if (word[ptr] < r.data)
  74.             delete(r.left, word, ptr);
  75.         else if (word[ptr] > r.data)
  76.             delete(r.right, word, ptr);
  77.         else
  78.         {
  79.  
  80.             if (r.isEnd && ptr == word.length - 1)
  81.                 r.isEnd = false;
  82.             else if (ptr + 1 < word.length)
  83.                 delete(r.middle, word, ptr + 1);
  84.         }
  85.     }
  86.  
  87.     public boolean search(String word)
  88.     {
  89.         return search(root, word.toCharArray(), 0);
  90.     }
  91.  
  92.     private boolean search(TSTNode r, char[] word, int ptr)
  93.     {
  94.         if (r == null)
  95.             return false;
  96.         if (word[ptr] < r.data)
  97.             return search(r.left, word, ptr);
  98.         else if (word[ptr] > r.data)
  99.             return search(r.right, word, ptr);
  100.         else
  101.         {
  102.             if (r.isEnd && ptr == word.length - 1)
  103.                 return true;
  104.             else if (ptr == word.length - 1)
  105.                 return false;
  106.             else
  107.                 return search(r.middle, word, ptr + 1);
  108.         }
  109.     }
  110.  
  111.     public String toString()
  112.     {
  113.         al = new ArrayList<String>();
  114.         traverse(root, "");
  115.         return "\nTernary Search Tree : " + al;
  116.     }
  117.  
  118.     private void traverse(TSTNode r, String str)
  119.     {
  120.         if (r != null)
  121.         {
  122.             traverse(r.left, str);
  123.             str = str + r.data;
  124.             if (r.isEnd)
  125.                 al.add(str);
  126.             traverse(r.middle, str);
  127.             str = str.substring(0, str.length() - 1);
  128.             traverse(r.right, str);
  129.         }
  130.     }
  131. }
  132.  
  133. public class TernaryTree
  134. {
  135.     public static void main(String[] args)
  136.     {
  137.         Scanner scan = new Scanner(System.in);
  138.  
  139.         TernarySearchTree tst = new TernarySearchTree();
  140.         System.out.println("Ternary Search Tree Test\n");
  141.         char ch;
  142.  
  143.         do
  144.         {
  145.             System.out.println("\nTernary Search Tree Operations\n");
  146.             System.out.println("1. insert word");
  147.             System.out.println("2. search word");
  148.             System.out.println("3. delete word");
  149.             System.out.println("4. check empty");
  150.             System.out.println("5. make empty");
  151.             int choice = scan.nextInt();
  152.             switch (choice)
  153.             {
  154.                 case 1:
  155.                     System.out.println("Enter word to insert");
  156.                     tst.insert(scan.next());
  157.                     break;
  158.                 case 2:
  159.                     System.out.println("Enter word to search");
  160.                     System.out.println("Search result : "
  161.                             + tst.search(scan.next()));
  162.                     break;
  163.                 case 3:
  164.                     System.out.println("Enter word to delete");
  165.                     tst.delete(scan.next());
  166.                     break;
  167.                 case 4:
  168.                     System.out.println("Empty Status : " + tst.isEmpty());
  169.                     break;
  170.                 case 5:
  171.                     System.out.println("Ternary Search Tree cleared");
  172.                     tst.makeEmpty();
  173.                     break;
  174.                 default:
  175.                     System.out.println("Wrong Entry \n ");
  176.                     break;
  177.             }
  178.             System.out.println(tst);
  179.             System.out.println("\nDo you want to continue (Type y or n) \n");
  180.             ch = scan.next().charAt(0);
  181.         } while (ch == 'Y' || ch == 'y');
  182.         scan.close();
  183.     }
  184. }

Output:

advertisement
$ javac TernaryTree.java
$ java TernaryTree
 
Ternary Tree Test
 
Ternary Search Tree Operations
 
1. insert word
2. search word
3. delete word
4. check empty
5. make empty
4
Empty Status : true
 
Ternary Search Tree : []
 
Do you want to continue (Type y or n) 
 
y
 
Ternary Search Tree Operations
 
1. insert word
2. search word
3. delete word
4. check empty
5. make empty
1
Enter word to insert
Sanfoundry 
 
Ternary Search Tree : [Sanfoundry]
 
Do you want to continue (Type y or n) 
 
 y
 
Ternary Search Tree Operations
 
1. insert word
2. search word
3. delete word
4. check empty
5. make empty
1
Enter word to insert
Technology
 
Ternary Search Tree : [Sanfoundry, Technology]
 
Do you want to continue (Type y or n) 
 
y
 
Ternary Search Tree Operations
 
1. insert word
2. search word
3. delete word
4. check empty
5. make empty
1
Enter word to insert
Solutions
 
Ternary Search Tree : [Sanfoundry, Solutions, Technology]
 
Do you want to continue (Type y or n) 
 
y
 
Ternary Search Tree Operations
 
1. insert word
2. search word
3. delete word
4. check empty
5. make empty
3
Enter word to delete
Solutions
 
Ternary Search Tree : [Sanfoundry, Technology]
 
Do you want to continue (Type y or n) 
 
y
 
Ternary Search Tree Operations
 
1. insert word
2. search word
3. delete word
4. check empty
5. make empty
1
Enter word to insert
Blog
 
Ternary Search Tree : [Blog, Sanfoundry, Technology]
 
Do you want to continue (Type y or n) 
 
y
 
Ternary Search Tree Operations
 
1. insert word
2. search word
3. delete word
4. check empty
5. make empty
2
Enter word to search
Sanfoundry
Search result : true
 
Ternary Search Tree : [Blog, Sanfoundry, Technology]
 
Do you want to continue (Type y or n) 
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Reference Books in Java 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 & technical discussions at Telegram SanfoundryClasses.