Data Structure: answer need to be in Java! Write program to create a Binary Sear
ID: 3685647 • Letter: D
Question
Data Structure: answer need to be in Java!
Write program to create a Binary Search Tree
1) Write a TreePrinter class that has a method that will print any arbitrary binary tree.
2) Need to print trees with height up to 5, i.e., 32 node value at the bottom row
3) Generate a Binary Search Tree that has height 5 and contains values from 10 through 99, using random numbers. d
4) Delete the root of the tree and print the tree after each deletion until tree is empty
5) Please provide sample input and output for each one
Explanation / Answer
Answer:
Code:
import java.io.*;
import java.util.*;
class BSTNode
{
int nodeData;
BSTNode lChild,rChild;
public BSTNode(int inData, BSTNode lc,BSTNode rc)
{
nodeData=inData;
lChild=lc;
rChild=rc;
}
public BSTNode(int inData)
{
nodeData=inData;
lChild=null;
rChild=null;
}
}
class BSTTree
{
BSTNode rootNode;
public BSTTree()
{
rootNode=null;
}
public boolean isEmpty()
{
return rootNode==null;
}
public void insertBSTTree(int inData)
{
rootNode=insertBSTTree(rootNode, inData);
}
public BSTNode insertBSTTree(BSTNode t, int inData)
{
if(t==null)
return new BSTNode(inData);
if(inData==t.nodeData)
return t;
if(inData<t.nodeData)
t.lChild=insertBSTTree(t.lChild,inData);
else
t.rChild=insertBSTTree(t.rChild,inData);
return t;
}
public void removeBSTTree()
{
if(isEmpty())
{
System.out.println("EMPTY TREE");
}
else
{
int val1 = rootNode.nodeData;
rootNode = removeBSTHelper(rootNode, val1);
}
}
private BSTNode removeBSTHelper(BSTNode node, int val1)
{
BSTNode temp1;
BSTNode temp2;
BSTNode curr;
if(node.nodeData == val1)
{
BSTNode lTree = node.lChild;
BSTNode rTree = node.rChild;
if(lTree == null && rTree == null)
{
return null;
}
else if(lTree == null)
{
temp1 = rTree;
return temp1;
}
else if(rTree == null)
{
temp1 = lTree;
return temp1;
}
else
{
temp2 = rTree;
temp1 = rTree;
while(temp1.lChild != null)
{
temp1 = temp1.lChild;
}
temp1.lChild = lTree;
return temp2;
}
}
if(val1 < node.nodeData)
{
curr = removeBSTHelper(node.lChild, val1);
node.lChild = curr;
}
else
{
curr = removeBSTHelper(node.rChild, val1);
node.rChild = curr;
}
return node;
}
public int getBSTHeight()
{
return getBSTHeightHelper(rootNode);
}
private int getBSTHeightHelper(BSTNode t)
{
if(t == null)
{
return -1;
}
else
{
return (1 + Math.max(getBSTHeightHelper(t.lChild), getBSTHeightHelper(t.rChild)));
}
}
}
class TreePrinter
{
BSTTree tree;
public TreePrinter(BSTTree inTree)
{
tree=inTree;
}
public void printTree()
{
printTree(tree.rootNode);
}
private void printTree(BSTNode t)
{
Queue<BSTNode> myQue = new LinkedList<>();
if(t==null)
{
System.out.println("Tree empty");
return ;
}
myQue.add(t);
while(!myQue.isEmpty()){
BSTNode n = myQue.poll();
System.out.print(n.nodeData + " ");
if(n.lChild!= null)
myQue.add(n.lChild);
if(n.rChild!= null)
myQue.add(n.rChild);
}
}
}
public class HelloWorld
{
public static void main(String[] args)
{
Random r=new Random();
BSTTree t=new BSTTree();
for(int kk=0;kk<32;kk++)
{
t.insertBSTTree(r.nextInt(99-10)+10);
}
TreePrinter treeprinter=new TreePrinter(t);
treeprinter.printTree();
while(t.isEmpty())
{
t.removeBSTTree();
}
System.out.println(t.isEmpty());
treeprinter=new TreePrinter(t);
treeprinter.printTree();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.