Question: Assignment 4: Written Assignment 1. Find Parent in a Binary Search Tree Here is a part of a recursive method for the BST class. It
Assignment 4:
Written Assignment
1.Find Parent in a Binary Search Tree
Here is a part of a recursive method for the BST class. It includes the method itself which calls a recursive Helper method. Your job is to complete the recursive Helper function. Youll know you have it correct or not, if you test it in a main program. Be sure to put the completed code in your BST class file. Hand in the written code of the complete FindParentHelper method on Tuesday, 14 November 2017 either by paper in class or by an attachment in an email. Be sure your name is on the paper.
Heres part of the code. You have to complete it.
public BSTNode FindParent(String item) {
return FindParentHelper(root,item);
}
public BSTNode FindParentHelper(BSTNode r, String item) {
if (r==null) return null;
if (r!=null) {
if(item.compareTo(r.datum)==0) return null;
if(item.compareTo(r.datum)<0) {
if(r.left!=null) {
if(item.compareTo(r.left.datum)==0) return r;
if(item.compareTo(r.left.datum)!=0)
return FindParentHelper(r.left,item);
}
}
//COMPLETE the rest of the method.
return null;
}
Heres a main program you can test it with:
public class BinarySearchTreeMain {
public static void main(String [] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.Insert("cat");
tree.Insert("ant");
tree.Insert("blabber");
tree.Insert("bat");
tree.Insert("dog");
tree.PrettyPrint(0);
BSTNode n=tree.FindParent("bat");
System.out.println("parent of bat is " + n.datum);
}
}
2.Find the Immediate Successor of an Item in a BST.
Be sure to put the completed code in your BST class file. Hand in the written code of the complete ImmediateSuccessor method on Tuesday, 14 November 2017 either by paper in class or by an attachment in an email. Be sure your name is on the paper.
Heres part of the code. You have to complete it.
private BSTNode ImmediateSuccessor(String s) {
//the closest number to the number we enter that is larger then
//the number we enter (that is, succeeds it)
//from the node we choose we move right one and then left all the
//way possible
BSTNode n=new BSTNode();
n = Find(s);
if (n.right == null)
{
return n;
} else {
n = n.right;
if (n.left == null) {
return n;
} else {
//Go left all the way until you cant go farther.
// You have to put in the correct loop.
return n;
}
}
}
--------------------------------------------------
BST v0.java File:
//Binary Search Tree class, version 0
class BSTv0
{
protected BSTNode root;
public BSTv0()
{
BSTNode root = new BSTNode();
};
// Insertion of an item into a BST whose root is "root".
// This will use a recursive "helper" method
public void Insert(String item)
{
root = InsertHelper(root, item);
}
private BSTNode InsertHelper(BSTNode r, String item)
{
if (r==null)
{
r = new BSTNode();
r.datum = item;
r.left = null;
r.right = null;
}
else
{
if (item.compareTo(r.datum)<0)
{
r.left = InsertHelper(r.left, item);// left subtree is where it goes
}
if (item.compareTo(r.datum)>0)
{
r.right = InsertHelper(r.right, item);
}
}
return r;
}
//FindParent
public BSTNode FindParent(String item)
{
return FindParentHelper(root,item);
}
//FindParentHelper
public BSTNode FindParentHelper(BSTNode r, String item)
{
if (r==null) return null;
if (r!=null)
{
if(item.compareTo(r.datum)==0) return null;
if(item.compareTo(r.datum)<0)
{
if(r.left!=null)
{
if(item.compareTo(r.left.datum)==0) return r;
if(item.compareTo(r.left.datum)!=0)
{
return FindParentHelper(r.left,item);
}
}
}
//COMPLETE the rest of the method.
return null;
}
//ImmediateSuccessor
private BSTNode ImmediateSuccessor(String s)
{
//the closest number to the number we enter that is larger then
//the number we enter (that is, succeeds it)
//from the node we choose we move right one and then left all the
//way possible
BSTNode n=new BSTNode();
n = Find(s);
if (n.right == null)
{
return n;
}
else
{
n = n.right;
if (n.left == null)
{
return n;
}
else
{
//Go left all the way until you cant go farther.
// You have to put in the correct loop.
return n;
}
}
}
//PrettyPrint
public void PrettyPrint(int level)
{
PrettyPrintHelper(root,level);
}
private void PrettyPrintHelper(BSTNode r, int level)
{
int i;
int TABSIZE=10;
if (r!=null)
{
PrettyPrintHelper(r.right, level+1);
for (i=1; i<=TABSIZE*level; i++)
{
System.out.print(" ");
}
System.out.println(r.datum);
PrettyPrintHelper(r.left, level+1);
}
}
}
---------------------------------------------------
BinarySearchTreeMain.java
public class BinarySearchTreeMain
{
public static void main(String [] args)
{
BinarySearchTree tree = new BinarySearchTree();
tree.Insert("cat");
tree.Insert("ant");
tree.Insert("blabber");
tree.Insert("bat");
tree.Insert("dog");
tree.PrettyPrint(0);
BSTNode n=tree.FindParent("bat");
System.out.println("parent of bat is " + n.datum);
}
}
------------------------------------------------------------
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help