Question: Java: There needs to be a BNode Class to complete this program. Create an appropreiate BNode class to make this code work below. import java.lang.*;
Java: There needs to be a BNode Class to complete this program. Create an appropreiate BNode class to make this code work below.
import java.lang.*;
public class BinarySearchTree
{
private static BNode root;
public BinarySearchTree()
{
root = null;
}
public void addNode(int n)
{
BNode current = root;
BNode newNode = new BNode();
newNode.data = n;
newNode.left = null;
newNode.right = null;
if(root == null)
{
root = newNode;
}
else
{
while(root != null)
{
if(newNode.data > current.data)
{
if(current.right == null)
{
current.right = newNode;
break;
}
else
{
current = current.right;
}
}
else
{
if(current.left == null)
{
current.left = newNode;
break;
}
else
{
current = current.left;
}
}
}
}
}
public static void inOrder(BNode node)
{
if(node == null)
return;
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
public static void printInOrder()
{
inOrder(root);
}
public static void preOrder(BNode node)
{
if(node == null)
return;
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
public static void printPreOrder()
{
preOrder(root);
}
public static void postOrder(BNode node)
{
if(node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data + " ");
}
public static void printPostOrder()
{
postOrder(root);
}
public static void revOrder(BNode node)
{
if(node == null)
return;
revOrder(node.right);
System.out.print(node.data + " ");
revOrder(node.left);
}
public static void printRevOrder()
{
revOrder(root);
}
public static BNode findMin()
{
BNode current = root;
if(current==null)
return current;
while(current.left != null)
current = current.left;
return current;
}
public static BNode findMax()
{
BNode current = root;
if(current==null)
return current;
while(current.right != null)
current = current.right;
return current;
}
public BNode searchTree(int n)
{
if (root == null)
return root;
BNode current = root;
BNode parent = root;
boolean currentIsLeft = true;
while (current.data != n)
{
parent = current;
if (current.data > n)
{
currentIsLeft = true;
current = current.left;
}
else
{
currentIsLeft = false;
current = current.right;
}
if (current == null)
return current;
if (current.left == null && current.right == null)
if (parent == current)
root = null;
else if (currentIsLeft)
parent.left = null;
else
parent.right = null;
else if (current.left == null)
if (parent == current)
root = current.right;
else if (currentIsLeft)
parent.left = current.right;
else
parent.right = current.right;
else if (current.right == null)
if (parent == current)
root = current.left;
else if (currentIsLeft)
parent.left = current.left;
else
parent.right = current.left;
else
{
BNode successor = getSuccessor(current);
if (parent == current)
root = successor;
else if (currentIsLeft)
parent.left = successor;
else
parent.right = successor;
successor.left = current.left;
}
}
return current;
}
private BNode getSuccessor(BNode removedNode)
{
BNode successorParent = removedNode;
BNode successor = removedNode;
BNode current = successor.right;
while (current != null)
{
successorParent = successor;
successor = current;
current = current.left;
}
if (successor != removedNode.right)
{
successorParent.left = successor.right;
successor.right = removedNode.right;
}
return successor;
}
public static void main(String args[])
{
BinarySearchTree bst = new BinarySearchTree();
int[] arr = {15, 9, 4, 13, 26, 32, 24};
for(int i=0; i bst.addNode(arr[i]); System.out.print("Print Inorder : "); printInOrder(); System.out.print(" Print Postorder : "); printPostOrder(); System.out.print(" Print Preorder : "); printPreOrder(); System.out.print(" Print Reverseorder : "); printRevOrder(); System.out.println(); BNode search = bst.searchTree(24); if (search != null) System.out.println("Found"); else System.out.println("Not Found"); search = bst.searchTree(28); if (search != null) System.out.println("Found"); else System.out.println("Not Found"); BNode min = findMin(); System.out.println("Min element : " + min.data); BNode max = findMax(); System.out.println("Max element : " + max.data); } }
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help