Write a java program for creating a binary search tree from an empty tree where you must consider 10 data items to form the tree.
-------------------------BSTNode.java---------------------
public class BSTNode<T> {
BSTNode left, right;
T data;
/* Constructor */
public BSTNode()
{
left = null;
right = null;
}
/* Constructor */
public BSTNode(T n)
{
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BSTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BSTNode n)
{
right = n;
}
/* Function to get left node */
public BSTNode getLeft()
{
return left;
}
/* Function to get right node */
public BSTNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(T d)
{
data = d;
}
/* Function to get data from node */
public T getData()
{
return data;
}
}
----------------------------BinarySearchTree.java----------------------------
import java.util.*;;
public class BinarySearchTree <T extends Comparable<T>>
{
private BSTNode<T> root;
private int size;
private Comparator<T> comparator;
public BinarySearchTree()
{
root = null;
size = 0;
comparator = null;
}
public int Size()
{
return size;
}
private int compare(T x, T y)
{
if(comparator == null)
return x.compareTo(y);
return comparator.compare(x,y);
}
/* ***************************************************************
* Insert a new node
* Returns true on successful insert otherwise false (when already present)
*****************************************************************/
public boolean insert(T data)
{
//TODO -> implement here
root = insert_util(root, data);
size++;
return true;
}
/* Function to insert data recursively */
private BSTNode insert_util(BSTNode<T> node, T data)
{
// if(node != null)
// System.out.println(compare(node.getData(), data));
// if tree is empty
if (node == null)
// create a new node
node = new BSTNode<T>(data);
// if the dat lies in the right subtree
else if (compare(node.getData(), data) < 0)
node.setRight(insert_util(node.getRight(), data));
// if the dat lies in the left subtree
else
node.setLeft(insert_util(node.getLeft(), data));
return node;
}
public boolean search(T val)
{
return search_util( this.root , val );
}
// search an element in the tree
private boolean search_util(BSTNode<T> r, T val)
{
if (r == null)
return false;
else if (compare(val, r.data) == 0)
return true;
else if (compare(val, r.data) < 0)
return search_util(r.left, val);
else
return search_util(r.right, val);
}
// get the node with minimum value
public BSTNode<T> getMin(BSTNode<T> x)
{
// moke trav point to the root of the tree
BSTNode trav = x;
// go tp the node at the extreme left
while (trav.getLeft() != null)
// move to the left child
trav = trav.getLeft();
return trav;
}
/*****************************************************************
* Delete a node
* Returns true on successful deletion and false otherwise
*****************************************************************/
public boolean delete(T data)
{
boolean found = search_util(root, data);
// if data is not present in the tree
if(found == false)
return found;
//TODO -> Implement here
BSTNode temp = root;
root = delete_util(temp, data);
size--;
return true;
}
// delete the given node
BSTNode<T> delete_util(BSTNode<T> x, T key)
{
// if the tree is empty
if(x == null)
return null;
// if the required node lies in the left subtree
//if (key < x.getData())
if (compare(key, x.getData()) < 0)
// recursively call the function on the left subtree
x.setLeft(delete_util(x.getLeft(), key));
// if the required node lies in the right subtree
//else if (key > x.getData())
else if (compare(key, x.getData()) > 0)
// recursively call the function on the right subtree
x.setRight(delete_util(x.getRight(), key));
// if the node to be deleted is found
else
{
// left child is not present
if (x.getLeft() == null)
return x.getRight();
// right child is not present
else if (x.getRight() == null)
return x.getLeft();
// no child is present
// get the node with the minimum value
BSTNode<T> trav = getMin(x.getRight());
// content of inorder successor is set to this node
x.setData(trav.getData());
// inorder successor is removed
x.setRight(delete_util(x.getRight(), trav.getData()));
}
return x;
}
/****************************************************************
*
* Reset Tree
*
***************************************************************/
public void reset()
{
root = null;
size=0;
}
/*****************************************************************
*
* Height of tree
*
****************************************************************/
public int height()
{
//TODO -> Implement here
return getHeight(root);
}
// get the height of the tree
public int getHeight(BSTNode<T> x)
{
// if tree is empty
if (x == null)
return 0;
else
{
// calculate height of right subtree
int r = getHeight(x.getRight());
// calculate height of left subtree
int l = getHeight(x.getLeft());
// if the height of left subtree is larger
if (l > r)
return(l + 1);
// if the height of right subtree is larger
return(r + 1);
}
}
/*****************************************************************
*
* Traversal
*
******************************************************************/
public void inorder()
{
System.out.print("inorder BST: ");
//TODO -> Implement here (print all nodes)
inorder_util(root);
System.out.println();
}
private void inorder_util(BSTNode<T> r)
{
if (r != null)
{
inorder_util(r.getLeft());
System.out.print(r.getData() +" ");
inorder_util(r.getRight());
}
}
public void preorder()
{
System.out.print("preorder BST: ");
//TODO -> Implement here
preorder_util(root);
System.out.println();
}
private void preorder_util(BSTNode<T> r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder_util(r.getLeft());
preorder_util(r.getRight());
}
}
public void postorder()
{
System.out.print("postorder BST: ");
//TODO -> Implement here
postorder_util(root);
System.out.println();
}
private void postorder_util(BSTNode<T> r)
{
if (r != null)
{
postorder_util(r.getLeft());
postorder_util(r.getRight());
System.out.print(r.getData() +" ");
}
}
}
---------------------------Test.java-----------------------
public class Test
{
public static void main(String[] args)
{
// create an empty tree by creating an object of class BinarySearchTree
BinarySearchTree<Integer> ob = new BinarySearchTree<Integer>();
ob.insert(25);
ob.insert(14);
ob.insert(36);
ob.insert(59);
ob.insert(18);
ob.insert(1);
ob.insert(56);
ob.insert(38);
System.out.println("Inorder Traversal ...");
ob.inorder();
System.out.println("Preorder Traversal ...");
ob.preorder();
System.out.println("Postorder Traversal ...");
ob.postorder();
System.out.println("Is 56 present in tree : " + ob.search(56));
ob.delete(56);
System.out.println("\nAfter deleting 56...\n\nInorder Traversal ...");
ob.inorder();
System.out.println("Preorder Traversal ...");
ob.preorder();
System.out.println("Postorder Traversal ...");
System.out.println("Is 56 present in tree : " + ob.search(56));
}
}
Sample Output
Write a java program for creating a binary search tree from an empty tree where you...
Consider the binary search tree created by inserting to empty tree the data in the following order: 15, 16, 4, 7, 2, 1, 3, 8, 10
Question 23 Not yet graded /0 pts Given a Binary Search Tree that is populated with numerical data, write an algorithm that will determine the sum, average, least and greatest of the values maintained in the tree. Express your algorithm in Java-like pseudodode. You may use any of the operations supported by the Binary Search Tree implementation used for Programming Project #5. Your solution must be developed at the application level. Your Answer For the next two questions you must...
IN JAVA create a binary search tree gui where you can insert and remove nodes, also move around the tree, thank you. The simpler the better.
IN JAVA 2 A Binary Search Tree The goal of this lab is to gain familiarity with simple binary search trees. 1. Begin this lab by implementing a simple class that represents a "node” in a binary search tree, as follows. public class MyTreeNode<t extends Comparable<T>> { public T data; public MyTreeNode<T> leftchild; public MyTreeNode<T> rightChild; public MyTreeNode<T> parent; 2. Have the second member of your pair type in the code for the simple binary search tree interface. public interface...
Trees Traversals Please write a Java program to traverse a binary tree in in-order and pre-order, and to plot a binary tree into a 2-dimensional array. You may write many recursive methods for this project. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Please stop your program if the user enters 0 as the tree selection. Your program must run the following Test Case 1 plus two more test cases to...
Tree Plot Please write a Java program to print or plot a binary tree in a 2-dimensional character format. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Your program must define 3 binary trees as follows. Each tree is defined in an integer 16 x 3 array. Programming Techniques: (1) The array for the binary tree can be integer data type with 16 rows by 3 columns. Please always make index...
Consider a binary search tree of positive integers without duplicates. Implement (write out) a program to find the second greatest element in the tree. The Second function is a member function of class BinarySearchTree. The function returns zero if the tree is empty or has only one element, otherwise it returns the value of the second greatest element. Based on the classes provided below, write the implementation of Second in the solution box, including any helper functions (if any) that...
Tree Plot Please write a Java program to print or plot a binary tree in a 2-dimensional character format. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Your program must define 3 binary trees as follows. Each tree is defined in an integer 16 x 3 array. Programming Techniques: (1) The array for the binary tree can be integer data type with 16 rows by 3 columns. Please always make index...
13inary Search Tree Using a binary search tree, you are tasked with building a dictionary program which you can store a word with its definition. Each node of the tree will contain the word and definition. The word is what will be used as the key to sort our data. The dictionary should allow you to search for a word. If the word exist then the definition will display. You can also add words to the dictionary. For testing you...
Trees Traversals Please write a Java program to traverse a binary tree in in-order and pre-order, and to plot a binary tree into a 2-dimensional array. You may write many recursive methods for this project. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Please stop your program if the user enters 0 as the tree selection. Your program must run the following Test Case 1 plus two more test cases to...