Code:
import java.util.Scanner;
import java.util.ArrayList;
/** class TSTNode **/
class TSTNode
{
char data;
boolean isEnd;
TSTNode left, middle, right;
/** Constructor **/
public TSTNode(char data)
{
this.data = data;
this.isEnd = false;
this.left = null;
this.middle = null;
this.right = null;
}
}
/** class TernarySearchTree **/
class TernarySearchTree
{
private TSTNode root;
private ArrayList
/** Constructor **/
public TernarySearchTree()
{
root = null;
}
/** function to check if empty **/
public boolean isEmpty()
{
return root == null;
}
/** function to clear **/
public void makeEmpty()
{
root = null;
}
/** function to insert for a word **/
public void insert(String word)
{
root = insert(root, word.toCharArray(), 0);
}
/** function to insert for a word **/
public TSTNode insert(TSTNode r, char[] word, int ptr)
{
if (r == null)
r = new TSTNode(word[ptr]);
if (word[ptr] < r.data)
r.left = insert(r.left, word, ptr);
else if (word[ptr] > r.data)
r.right = insert(r.right, word, ptr);
else
{
if (ptr + 1 < word.length)
r.middle = insert(r.middle, word, ptr + 1);
else
r.isEnd = true;
}
return r;
}
/** function to delete a word **/
public void delete(String word)
{
delete(root, word.toCharArray(), 0);
}
/** function to delete a word **/
private void delete(TSTNode r, char[] word, int ptr)
{
if (r == null)
return;
if (word[ptr] < r.data)
delete(r.left, word, ptr);
else if (word[ptr] > r.data)
delete(r.right, word, ptr);
else
{
/** to delete a word just make isEnd false **/
if (r.isEnd && ptr == word.length - 1)
r.isEnd = false;
else if (ptr + 1 < word.length)
delete(r.middle, word, ptr + 1);
}
}
/** function to search for a word **/
public boolean search(String word)
{
return search(root, word.toCharArray(), 0);
}
/** function to search for a word **/
private boolean search(TSTNode r, char[] word, int ptr)
{
if (r == null)
return false;
if (word[ptr] < r.data)
return search(r.left, word, ptr);
else if (word[ptr] > r.data)
return search(r.right, word, ptr);
else
{
if (r.isEnd && ptr == word.length - 1)
return true;
else if (ptr == word.length - 1)
return false;
else
return search(r.middle, word, ptr + 1);
}
}
/** function to print tree **/
public String toString()
{
al = new ArrayList
traverse(root, "");
return "\nTernary Search Tree : "+ al;
}
/** function to traverse tree **/
private void traverse(TSTNode r, String str)
{
if (r != null)
{
traverse(r.left, str);
str = str + r.data;
if (r.isEnd)
al.add(str);
traverse(r.middle, str);
str = str.substring(0, str.length() - 1);
traverse(r.right, str);
}
}
}
/** class TernarySearchTree **/
public class TernarySearchTreeTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of TernarySearchTree */
TernarySearchTree tst = new TernarySearchTree();
System.out.println("Ternary Search Tree Test\n");
char ch;
/* Perform tree operations */
do
{
System.out.println("\nTernary Search Tree Operations\n");
System.out.println("1. insert word");
System.out.println("2. search word");
System.out.println("3. delete word");
System.out.println("4. check empty");
System.out.println("5. make empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter word to insert");
tst.insert( scan.next() );
break;
case 2 :
System.out.println("Enter word to search");
System.out.println("Search result : "+ tst.search( scan.next() ));
break;
case 3 :
System.out.println("Enter word to delete");
tst.delete( scan.next() );
break;
case 4 :
System.out.println("Empty Status : "+ tst.isEmpty() );
break;
case 5 :
System.out.println("Ternary Search Tree cleared");
tst.makeEmpty();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
System.out.println(tst);
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Output:
Ternary Search 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
apple
Ternary Search Tree : [apple]
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
pine
Ternary Search Tree : [apple, pine]
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
pineapple
Ternary Search Tree : [apple, pine, pineapple]
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
pin
Ternary Search Tree : [apple, pin, pine, pineapple]
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
in
Ternary Search Tree : [apple, in, pin, pine, pineapple]
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
i
Ternary Search Tree : [apple, i, in, pin, pine, pineapple]
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
mango
Ternary Search Tree : [apple, i, in, mango, pin, pine, pineapple]
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
man
Ternary Search Tree : [apple, i, in, man, mango, pin, pine, pineapple]
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
an
Ternary Search Tree : [an, apple, i, in, man, mango, pin, pine, pineapple]
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
a
Ternary Search Tree : [a, an, apple, i, in, man, mango, pin, pine, pineapple]
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
pin
Search result : true
Ternary Search Tree : [a, an, apple, i, in, man, mango, pin, pine, pineapple]
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
pines
Search result : false
Ternary Search Tree : [a, an, apple, i, in, man, mango, pin, pine, pineapple]
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
pine
Search result : true
Ternary Search Tree : [a, an, apple, i, in, man, mango, pin, pine, pineapple]
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
i
Ternary Search Tree : [a, an, apple, in, man, mango, pin, pine, pineapple]
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
i
Search result : false
Ternary Search Tree : [a, an, apple, in, man, mango, pin, pine, pineapple]
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
in
Ternary Search Tree : [a, an, apple, man, mango, pin, pine, pineapple]
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
apple
Ternary Search Tree : [a, an, man, mango, pin, pine, pineapple]
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
pineapple
Ternary Search Tree : [a, an, man, mango, pin, pine]
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
apple
Search result : false
Ternary Search Tree : [a, an, man, mango, pin, pine]
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
4
Empty Status : false
Ternary Search Tree : [a, an, man, mango, pin, pine]
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
5
Ternary Search Tree cleared
Ternary Search Tree : []
Do you want to continue (Type y or n)
n
More Java Programs:
