Ternary Tree Program in Java

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.

//This is a java program to implement Ternary Tree

```
import java.util.Scanner;
```
```
import java.util.ArrayList;
```
```
 
```
```
class TSTNode
```
```
{
```
```
    char    data;
```
```
    boolean isEnd;
```
```
    TSTNode left, middle, right;
```
```
 
```
```
    public TSTNode(char data)
```
```
    {
```
```
        this.data = data;
```
```
        this.isEnd = false;
```
```
        this.left = null;
```
```
        this.middle = null;
```
```
        this.right = null;
```
```
    }
```
```
}
```
```
 
```
```
class TernarySearchTree
```
```
{
```
```
    private TSTNode           root;
```
```
    private ArrayList<String> al;
```
```
 
```
```
    public TernarySearchTree()
```
```
    {
```
```
        root = null;
```
```
    }
```
```
 
```
```
    public boolean isEmpty()
```
```
    {
```
```
        return root == null;
```
```
    }
```
```
 
```
```
    public void makeEmpty()
```
```
    {
```
```
        root = null;
```
```
    }
```
```
 
```
```
    public void insert(String word)
```
```
    {
```

        root = insert(root, word.toCharArray(), 0);

```
    }
```
```
 
```

    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;
```
```
    }
```
```
 
```
```
    public void delete(String word)
```
```
    {
```

        delete(root, word.toCharArray(), 0);

```
    }
```
```
 
```

    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
```
```
        {
```
```
 
```

            if (r.isEnd && ptr == word.length - 1)

```
                r.isEnd = false;
```

            else if (ptr + 1 < word.length)

                delete(r.middle, word, ptr + 1);

```
        }
```
```
    }
```
```
 
```
```
    public boolean search(String word)
```
```
    {
```

        return search(root, word.toCharArray(), 0);

```
    }
```
```
 
```

    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);

```
        }
```
```
    }
```
```
 
```
```
    public String toString()
```
```
    {
```
```
        al = new ArrayList<String>();
```
```
        traverse(root, "");
```

        return "\nTernary Search Tree : " + al;

```
    }
```
```
 
```

    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);
```
```
        }
```
```
    }
```
```
}
```
```
 
```
```
public class TernaryTree
```
```
{
```

    public static void main(String[] args)

```
    {
```

        Scanner scan = new Scanner(System.in);

```
 
```

        TernarySearchTree tst = new TernarySearchTree();

        System.out.println("Ternary Search Tree Test\n");

```
        char ch;
```
```
 
```
```
        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');

```
        scan.close();
```
```
    }
```
```
}
```

Output:

$ 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.

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

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Check if a Binary Tree is Subtree of Another Binary Tree

» Next - Java Program to Perform Right and Left Rotation on a Binary Search Tree

Related Posts:

Check Data Structure Books
Check Computer Science Books
Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Practice Computer Science MCQs

Recommended Articles: