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:
An Intro to Spring Cloud Vault
An Example of Load Balancing with Zuul and Eureka
Java Program to Implement Hash Tables with Double Hashing
XML-Based Injection in Spring
Xử lý ngoại lệ đối với trường hợp ghi đè phương thức trong java
Java Program to find the maximum subarray sum O(n^2) time(naive method)
Java Program to subtract two large numbers using Linked Lists
Hướng dẫn sử dụng Lớp FilePermission trong java
Life Cycle of a Thread in Java
Spring RequestMapping
Spring Security 5 – OAuth2 Login
Java Program to Check Multiplicability of Two Matrices
Spring Boot Application as a Service
Spring @RequestParam Annotation
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
The HttpMediaTypeNotAcceptableException in Spring MVC
Java – InputStream to Reader
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Flattening Nested Collections in Java
Hướng dẫn sử dụng Java Reflection
Java Program to Evaluate an Expression using Stacks
Java Program to Implement ArrayDeque API
Guava CharMatcher
Java Program to Implement LinkedTransferQueue API
4 tính chất của lập trình hướng đối tượng trong Java
Sort a HashMap in Java
Java Program to Find Number of Articulation points in a Graph
Marker Interface trong Java
Multipart Upload with HttpClient 4
Java Program to Implement DelayQueue API
Deploy a Spring Boot WAR into a Tomcat Server
Hướng dẫn Java Design Pattern – Transfer Object