October 9, 2010
Ternary Search Tree Java
Problem
Write a java program to construct and print a ternary Tree. A ternary tree is similar to a binary tree except a parent node can have up to three children instead of two. The left child value is less than the parent value, the right is greater than the parent value and the middle value is equal to the parent value.
Solution
We need to have a Node data structure that has three child nodes and one value. Populating and printing the tree can be achieved using recursive calls. For more details you can take a look at the commented source code below.
Code
Here is the code in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
//Main class public class TrinaryTree { //Main function public static void main(String[] args) { //Sample tree values rooted at 5 int Values[] = {5, 4, 9, 5, 7, 2, 2}; //Create Tree TrinaryTree tree = new TrinaryTree(); //Populate tree tree.Populate(Values, 7); } //Define a tree node static class Node { //Left is less than node value Node left; //Middle is equal to node value Node middle; //Right is greater than node value Node right; //Node value int value; //Constructor public Node(int value) { this.value = value; } } //Populate method: receives an //array of integers along with //its size (n) public void Populate(int A[], int n) { //Tree rooted at the first //element of the array Node root = new Node(A[0]); //Insert values into the tree for (int i = 1; i < n; i++) { Insert(root, A[i]); } //Print tree Print(root); } //Insert a node into the tree public void Insert(Node node, int value) { //If the value to be inserted //is less than node value then //we either inserts it as the //left child if it does not exist //or recursively call the insert //on the left child if it does exist if (value < node.value) { //Left child exist if (node.left != null) { Insert(node.left, value); } //Left child does not exist //so create it else { node.left = new Node(value); } } //Same reasoning as above but for right else if (value > node.value) { if (node.right != null) { Insert(node.right, value); } else { node.right = new Node(value); } } //Same reasoning as above but for middle else { if (node.middle != null) { Insert(node.middle, value); } else { node.middle = new Node(value); } } } //Recursive method to print the //whole tree public void Print(Node root) { if (root != null) { System.out.println("Node value : " + root.value); Print(root.left); Print(root.middle); Print(root.right); } } } |
About Author
Mohammed Abualrob
Software Engineer @ Cisco