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.
//This is a java program to perform sorting using BTree, Inorder traversal of BST results in sorting of numbers import java.util.Random; /* Class BSTNode */ class BSTNodes { BSTNodes left, right; int data; /* Constructor */ public BSTNodes() { left = null; right = null; data = 0; } /* Constructor */ public BSTNodes(int n) { left = null; right = null; data = n; } /* Function to set left node */ public void setLeft(BSTNodes n) { left = n; } /* Function to set right node */ public void setRight(BSTNodes n) { right = n; } /* Function to get left node */ public BSTNodes getLeft() { return left; } /* Function to get right node */ public BSTNodes getRight() { return right; } /* Function to set data to node */ public void setData(int d) { data = d; } /* Function to get data from node */ public int getData() { return data; } } /* Class BST */ class BT { private BSTNode root; /* Constructor */ public BT() { root = null; } /* Function to check if tree is empty */ public boolean isEmpty() { return root == null; } /* Functions to insert data */ public void insert(int data) { root = insert(root, data); } /* Function to insert data recursively */ private BSTNode insert(BSTNode node, int data) { if (node == null) node = new BSTNode(data); else { if (data <= node.getData()) node.left = insert(node.left, data); else node.right = insert(node.right, data); } return node; } /* Functions to delete data */ public void delete(int k) { if (isEmpty()) System.out.println("Tree Empty"); else if (search(k) == false) System.out.println("Sorry " + k + " is not present"); else { root = delete(root, k); System.out.println(k + " deleted from the tree"); } } private BSTNode delete(BSTNode root, int k) { BSTNode p, p2, n; if (root.getData() == k) { BSTNode lt, rt; lt = root.getLeft(); rt = root.getRight(); if (lt == null && rt == null) return null; else if (lt == null) { p = rt; return p; } else if (rt == null) { p = lt; return p; } else { p2 = rt; p = rt; while (p.getLeft() != null) p = p.getLeft(); p.setLeft(lt); return p2; } } if (k < root.getData()) { n = delete(root.getLeft(), k); root.setLeft(n); } else { n = delete(root.getRight(), k); root.setRight(n); } return root; } /* Functions to count number of nodes */ public int countNodes() { return countNodes(root); } /* Function to count number of nodes recursively */ private int countNodes(BSTNode r) { if (r == null) return 0; else { int l = 1; l += countNodes(r.getLeft()); l += countNodes(r.getRight()); return l; } } /* Functions to search for an element */ public boolean search(int val) { return search(root, val); } /* Function to search for an element recursively */ private boolean search(BSTNode r, int val) { boolean found = false; while ((r != null) && !found) { int rval = r.getData(); if (val < rval) r = r.getLeft(); else if (val > rval) r = r.getRight(); else { found = true; break; } found = search(r, val); } return found; } /* Function for inorder traversal */ public void inorder() { inorder(root); } private void inorder(BSTNode r) { if (r != null) { inorder(r.getLeft()); System.out.print(r.getData() + " "); inorder(r.getRight()); } } /* Function for preorder traversal */ public void preorder() { preorder(root); } private void preorder(BSTNode r) { if (r != null) { System.out.print(r.getData() + " "); preorder(r.getLeft()); preorder(r.getRight()); } } /* Function for postorder traversal */ public void postorder() { postorder(root); } private void postorder(BSTNode r) { if (r != null) { postorder(r.getLeft()); postorder(r.getRight()); System.out.print(r.getData() + " "); } } } public class Sort_BTree { public static int N = 20; public static void main(String args[]) { Random random = new Random(); BT bt = new BT(); System.out .println("Sorting of randomly generated numbers using B TREE"); for (int i = 0; i < N; i++) bt.insert(Math.abs(random.nextInt(100))); System.out.println("The elements of the tree: "); bt.preorder(); System.out.println("\nThe sorted sequence is: "); bt.inorder(); } }
Output:
$ 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
Related posts:
Spring Data – CrudRepository save() Method
The DAO with JPA and Spring
Encode a String to UTF-8 in Java
Connect through a Proxy
Sorting in Java
Java Program to Implement Rope
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Java Program to Implement Interpolation Search Algorithm
Java Program to Implement VList
Properties with Spring and Spring Boot
Retrieve User Information in Spring Security
Assert an Exception is Thrown in JUnit 4 and 5
Giới thiệu Json Web Token (JWT)
Spring Boot - Tomcat Deployment
RegEx for matching Date Pattern in Java
Sorting Query Results with Spring Data
Java Program to Implement Skip List
Instance Profile Credentials using Spring Cloud
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Giới thiệu luồng vào ra (I/O) trong Java
A Guide to WatchService in Java NIO2
Java Program to Implement HashTable API
The HttpMediaTypeNotAcceptableException in Spring MVC
Quick Guide to @RestClientTest in Spring Boot
Use Liquibase to Safely Evolve Your Database Schema
JUnit 5 for Kotlin Developers
Java Program to Show the Duality Transformation of Line and Point
An Introduction to Java.util.Hashtable Class
LIKE Queries in Spring JPA Repositories
Java Program to Implement Merge Sort Algorithm on Linked List
Comparing Two HashMaps in Java
Java Program to Repeatedly Search the Same Text (such as Bible by building a Data Structure)