Java Program to Perform Sorting Using B-Tree

«
»
This is a java program to implement sorting using B-Trees. Binary Search Trees are the type of B trees that self organizes. Inorder traversal of BSTs results in the sorted sequence of elements in the tree.

Here is the source code of the Java Program to Perform Sorting Using B-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 perform sorting using BTree, Inorder traversal of BST results in sorting of numbers
  2. import java.util.Random;
  3.  
  4. /* Class BSTNode */
  5. class BSTNodes {
  6.     BSTNodes left, right;
  7.     int data;
  8.  
  9.     /* Constructor */
  10.     public BSTNodes() 
  11.     {
  12.         left = null;
  13.         right = null;
  14.         data = 0;
  15.     }
  16.  
  17.     /* Constructor */
  18.     public BSTNodes(int n) 
  19.     {
  20.         left = null;
  21.         right = null;
  22.         data = n;
  23.     }
  24.  
  25.     /* Function to set left node */
  26.     public void setLeft(BSTNodes n) 
  27.     {
  28.         left = n;
  29.     }
  30.  
  31.     /* Function to set right node */
  32.     public void setRight(BSTNodes n) 
  33.     {
  34.         right = n;
  35.     }
  36.  
  37.     /* Function to get left node */
  38.     public BSTNodes getLeft() 
  39.     {
  40.         return left;
  41.     }
  42.  
  43.     /* Function to get right node */
  44.     public BSTNodes getRight() 
  45.     {
  46.         return right;
  47.     }
  48.  
  49.     /* Function to set data to node */
  50.     public void setData(int d) 
  51.     {
  52.         data = d;
  53.     }
  54.  
  55.     /* Function to get data from node */
  56.     public int getData() 
  57.     {
  58.         return data;
  59.     }
  60. }
  61.  
  62. /* Class BST */
  63. class BT {
  64.     private BSTNode root;
  65.  
  66.     /* Constructor */
  67.     public BT() 
  68.     {
  69.         root = null;
  70.     }
  71.  
  72.     /* Function to check if tree is empty */
  73.     public boolean isEmpty() 
  74.     {
  75.         return root == null;
  76.     }
  77.  
  78.     /* Functions to insert data */
  79.     public void insert(int data) 
  80.     {
  81.         root = insert(root, data);
  82.     }
  83.  
  84.     /* Function to insert data recursively */
  85.     private BSTNode insert(BSTNode node, int data) 
  86.     {
  87.         if (node == null)
  88.             node = new BSTNode(data);
  89.         else 
  90.         {
  91.             if (data <= node.getData())
  92.                 node.left = insert(node.left, data);
  93.             else
  94.                 node.right = insert(node.right, data);
  95.         }
  96.         return node;
  97.     }
  98.  
  99.     /* Functions to delete data */
  100.     public void delete(int k)
  101.     {
  102.         if (isEmpty())
  103.             System.out.println("Tree Empty");
  104.         else if (search(k) == false)
  105.             System.out.println("Sorry " + k + " is not present");
  106.         else 
  107.         {
  108.             root = delete(root, k);
  109.             System.out.println(k + " deleted from the tree");
  110.         }
  111.     }
  112.  
  113.     private BSTNode delete(BSTNode root, int k) 
  114.     {
  115.         BSTNode p, p2, n;
  116.         if (root.getData() == k) 
  117.         {
  118.             BSTNode lt, rt;
  119.             lt = root.getLeft();
  120.             rt = root.getRight();
  121.             if (lt == null && rt == null)
  122.                 return null;
  123.             else if (lt == null) 
  124.             {
  125.                 p = rt;
  126.                 return p;
  127.             }
  128.             else if (rt == null) 
  129.             {
  130.                 p = lt;
  131.                 return p;
  132.             } 
  133.             else 
  134.             {
  135.                 p2 = rt;
  136.                 p = rt;
  137.                 while (p.getLeft() != null)
  138.                     p = p.getLeft();
  139.                 p.setLeft(lt);
  140.                 return p2;
  141.             }
  142.         }
  143.         if (k < root.getData()) 
  144.         {
  145.             n = delete(root.getLeft(), k);
  146.             root.setLeft(n);
  147.         }
  148.         else 
  149.         {
  150.             n = delete(root.getRight(), k);
  151.             root.setRight(n);
  152.         }
  153.         return root;
  154.     }
  155.  
  156.     /* Functions to count number of nodes */
  157.     public int countNodes() 
  158.     {
  159.         return countNodes(root);
  160.     }
  161.  
  162.     /* Function to count number of nodes recursively */
  163.     private int countNodes(BSTNode r) 
  164.     {
  165.         if (r == null)
  166.             return 0;
  167.         else 
  168.         {
  169.             int l = 1;
  170.             l += countNodes(r.getLeft());
  171.             l += countNodes(r.getRight());
  172.             return l;
  173.         }
  174.     }
  175.  
  176.     /* Functions to search for an element */
  177.     public boolean search(int val) 
  178.     {
  179.         return search(root, val);
  180.     }
  181.  
  182.     /* Function to search for an element recursively */
  183.     private boolean search(BSTNode r, int val) 
  184.     {
  185.         boolean found = false;
  186.         while ((r != null) && !found) 
  187.         {
  188.             int rval = r.getData();
  189.             if (val < rval)
  190.                 r = r.getLeft();
  191.             else if (val > rval)
  192.                 r = r.getRight();
  193.             else 
  194.             {
  195.                 found = true;
  196.                 break;
  197.             }
  198.             found = search(r, val);
  199.         }
  200.         return found;
  201.     }
  202.  
  203.     /* Function for inorder traversal */
  204.     public void inorder() 
  205.     {
  206.         inorder(root);
  207.     }
  208.  
  209.     private void inorder(BSTNode r) 
  210.     {
  211.         if (r != null) 
  212.         {
  213.             inorder(r.getLeft());
  214.             System.out.print(r.getData() + " ");
  215.             inorder(r.getRight());
  216.         }
  217.     }
  218.  
  219.     /* Function for preorder traversal */
  220.     public void preorder() 
  221.     {
  222.         preorder(root);
  223.     }
  224.  
  225.     private void preorder(BSTNode r) 
  226.     {
  227.         if (r != null) 
  228.         {
  229.             System.out.print(r.getData() + " ");
  230.             preorder(r.getLeft());
  231.             preorder(r.getRight());
  232.         }
  233.     }
  234.  
  235.     /* Function for postorder traversal */
  236.     public void postorder() 
  237.     {
  238.         postorder(root);
  239.     }
  240.  
  241.     private void postorder(BSTNode r) 
  242.     {
  243.         if (r != null) 
  244.         {
  245.             postorder(r.getLeft());
  246.             postorder(r.getRight());
  247.             System.out.print(r.getData() + " ");
  248.         }
  249.     }
  250. }
  251.  
  252. public class Sort_BTree 
  253. {
  254.     public static int N = 20;
  255.  
  256.     public static void main(String args[]) 
  257.     {
  258.         Random random = new Random();
  259.         BT bt = new BT();
  260.  
  261.         System.out
  262.                 .println("Sorting of randomly generated numbers using B TREE");
  263.  
  264.         for (int i = 0; i < N; i++)
  265.             bt.insert(Math.abs(random.nextInt(100)));
  266.  
  267.         System.out.println("The elements of the tree: ");
  268.         bt.preorder();
  269.  
  270.         System.out.println("\nThe sorted sequence is: ");
  271.         bt.inorder();
  272.     }
  273. }

Output:

advertisement
$ javac Sort_BTree.java
$ java Sort_BTree
 
Sorting of randomly generated numbers using B TREE
The elements of the tree: 
45 23 3 4 26 39 32 30 32 83 64 50 47 54 64 67 75 88 94 95 
The sorted sequence is: 
3 4 23 26 30 32 32 39 45 47 50 54 64 64 67 75 83 88 94 95

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

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

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter