Java Program to Implement Threaded Binary Tree

This is a Java Program to implement Threaded Binary Tree. A threaded binary tree makes it possible to traverse the values in the binary tree via a linear traversal that is more rapid than a recursive in-order traversal. It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly. This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).

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

  1. /**
  2.  *    Java Program to Implement Threaded Binary Tree
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class TBSTNode **/
  8. class TBSTNode
  9. {
  10.     int ele;
  11.     TBSTNode left, right;
  12.     boolean leftThread, rightThread;
  13.  
  14.     /** Constructor **/
  15.     public TBSTNode(int ele)
  16.     {
  17.         this(ele, null, null, true, true);
  18.     }
  19.  
  20.     /** Constructor **/
  21.     public TBSTNode(boolean leftThread, boolean rightThread)
  22.     {
  23.         this.ele = Integer.MAX_VALUE;
  24.         this.left = this;
  25.         this.right = this;
  26.         this.leftThread = leftThread;
  27.         this.rightThread = rightThread;
  28.     }
  29.  
  30.     /** Constructor **/
  31.     public TBSTNode(int ele, TBSTNode left, TBSTNode right, boolean leftThread, boolean rightThread)
  32.     {
  33.         this.ele = ele;
  34.         this.left = left;
  35.         this.right = right;
  36.         this.leftThread = leftThread;
  37.         this.rightThread = rightThread;
  38.     }
  39. }
  40.  
  41. /** Class ThreadedBinarySearchTree **/
  42. class ThreadedBinarySearchTree
  43. {
  44.     private TBSTNode root;
  45.  
  46.     /** Constructor **/
  47.     public ThreadedBinarySearchTree () 
  48.     {
  49.         root = new TBSTNode(true, false);      
  50.     }
  51.  
  52.     /** Function to clear tree **/
  53.     public void clear()
  54.     {
  55.         root = new TBSTNode(true, false);  
  56.     }
  57.  
  58.     /** Function to insert an element **/
  59.     public void insert(int ele) 
  60.     {
  61.         TBSTNode ptr = findNode(root, ele);
  62.  
  63.         /** element already present **/
  64.         if (ptr == null)
  65.             return;         
  66.  
  67.         if (ptr.ele < ele) 
  68.         { 
  69.             TBSTNode nptr = new TBSTNode(ele, ptr, ptr.right, true, true);            
  70.             ptr.right = nptr;
  71.             ptr.rightThread = false;
  72.         }
  73.         else
  74.         {
  75.             TBSTNode nptr = new TBSTNode(ele, ptr.left, ptr, true, true);         
  76.             ptr.left = nptr;
  77.             ptr.leftThread = false;
  78.         }
  79.     }
  80.  
  81.     /** function to find node **/
  82.     public TBSTNode findNode(TBSTNode r, int ele)
  83.     {
  84.         if (r.ele < ele)
  85.         {
  86.             if (r.rightThread)
  87.                 return r;
  88.             return findNode(r.right, ele);
  89.         }
  90.         else if (r.ele > ele)
  91.         {
  92.             if (r.leftThread)
  93.                 return r;
  94.             return findNode(r.left, ele);
  95.         }
  96.         else
  97.             return null;        
  98.     }
  99.  
  100.     /** Function to search for an element **/
  101.     public boolean search(int ele) 
  102.     {
  103.         return findNode(root, ele) == null;
  104.     }
  105.  
  106.     /** Function to print tree **/
  107.     public void inOrder() 
  108.     {
  109.         TBSTNode temp = root;
  110.         for (;;)
  111.         {
  112.             temp = insucc(temp);
  113.             if (temp == root)
  114.                 break;
  115.             System.out.print(temp.ele +" ");
  116.         }
  117.     } 
  118.  
  119.     /** Function to get inorder successor **/
  120.     public TBSTNode insucc(TBSTNode tree)
  121.     {
  122.         TBSTNode temp;
  123.         temp = tree.right;
  124.         if (!tree.rightThread)
  125.             while (!temp.leftThread)
  126.                 temp = temp.left;
  127.         return temp;
  128.     }
  129. }
  130.  
  131. /** Class ThreadedBinarySearchTreeTest **/
  132. public class ThreadedBinarySearchTreeTest
  133. {
  134.     public static void main(String[] args)
  135.     {                 
  136.         Scanner scan = new Scanner(System.in);
  137.         /** Creating object of ThreadedBinarySearchTree **/
  138.         ThreadedBinarySearchTree tbst = new ThreadedBinarySearchTree(); 
  139.         System.out.println("Threaded Binary Search Tree Test\n");          
  140.         char ch;
  141.         /**  Perform tree operations  **/
  142.         do    
  143.         {
  144.             System.out.println("\nThreaded Binary Search Tree Operations\n");
  145.             System.out.println("1. insert ");
  146.             System.out.println("2. search");
  147.             System.out.println("3. clear"); 
  148.  
  149.             int choice = scan.nextInt();            
  150.             switch (choice)
  151.             {
  152.             case 1 : 
  153.                 System.out.println("Enter integer element to insert");
  154.                 tbst.insert( scan.nextInt() );                     
  155.                 break;                          
  156.             case 2 : 
  157.                 System.out.println("Enter integer element to search");
  158.                 System.out.println("Search result : "+ tbst.search( scan.nextInt() ));
  159.                 break;       
  160.             case 3 : 
  161.                 System.out.println("\nTree Cleared\n");
  162.                 tbst.clear();
  163.                 break;           
  164.             default : 
  165.                 System.out.println("Wrong Entry \n ");
  166.                 break;   
  167.             }
  168.             /**  Display tree  **/ 
  169.             System.out.print("\nTree = ");
  170.             tbst.inOrder();            
  171.             System.out.println();
  172.  
  173.             System.out.println("\nDo you want to continue (Type y or n) \n");
  174.             ch = scan.next().charAt(0);                        
  175.         } while (ch == 'Y'|| ch == 'y');               
  176.     }
  177. }

Threaded Binary Search Tree Test
 
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
1
Enter integer element to insert
28
 
Tree = 28
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
1
Enter integer element to insert
5
 
Tree = 5 28
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
1
Enter integer element to insert
19
 
Tree = 5 19 28
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
1
Enter integer element to insert
63
 
Tree = 5 19 28 63
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
1
Enter integer element to insert
14
 
Tree = 5 14 19 28 63
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
1
Enter integer element to insert
7
 
Tree = 5 7 14 19 28 63
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
1
Enter integer element to insert
70
 
Tree = 5 7 14 19 28 63 70
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
2
Enter integer element to search
24
Search result : false
 
Tree = 5 7 14 19 28 63 70
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
2
Enter integer element to search
28
Search result : true
 
Tree = 5 7 14 19 28 63 70
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
2
Enter integer element to search
14
Search result : true
 
Tree = 5 7 14 19 28 63 70
 
Do you want to continue (Type y or n)
 
y
 
Threaded Binary Search Tree Operations
 
1. insert
2. search
3. clear
3
 
Tree Cleared
 
 
Tree =
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

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

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