Write the Java source code necessary to build a solution for the problem below:
ID: 3567470 • Letter: W
Question
Write the Java source code necessary to build a solution for the problem below:
You are about to start a new "Thank You Note" service and you are seeking a way to store the names of the people to whom the notes must be sent in a way that reflects the order that the gifts arrived. You searched the web and found that storing things in a binary tree is a very efficient way to do this so you begin to experiment. To explore the possibilities, you create a binary search tree and make an attempt to store the names as you think they should be stored. To test the search scheme that best reflects the order of the gifts arrival, you store the names of the sender and then do three searches to determine the best match. Remember, you have put the names in the list that is stored in the tree in the order in which they arrived. Which tree traversal algorithm best matches the list that you want to print?
To solve the problem, create a binary search tree from an array of the following names: Daniel, George, Adam, Peter, Michael, Jones, Tom, Allison, James, and Brian. Perform a preorder, inorder and postorder traversal on the binary tree and print the names in the order of the traversal. Remove Peter and Brian from the tree and perform the traversal again. What do you observe when an inorder traversal is performed on the binary tree?
Explanation / Answer
The preorder algorithm will produces the best result the way in which the items are inserted.
Program Code:
import java.util.Scanner;
/* Class BSTNode */
public class BSTNode
{
BSTNode left, right;
String data;
/* Constructor */
public BSTNode()
{
left = null;
right = null;
data = null;
}
/* Constructor */
public BSTNode(String d)
{
left = null;
right = null;
data = d;
}
/* 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(String d)
{
data = d;
}
/* Function to get data from node */
public String getData()
{
return data;
}
}
/* Class BSTree */
public class BSTree
{
private BSTNode root;
//Constructor
public BSTree()
{
root = null;
}
//isEmpty function to check the tree is empty or not
public boolean isEmpty()
{
return root == null;
}
//insert function
public void insert(String data)
{
root = insert(root, data);
}
// recursive insert function
private BSTNode insert(BSTNode node, String data)
{
if (node == null)
node = new BSTNode(data);
else
{
if (data.compareTo(node.getData())>0)
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
//delete function
public void delete(String 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, String k)
{
BSTNode p1node, p2node, pnode;
if (root.getData().equalsIgnoreCase( k))
{
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null)
{
p1node = rt;
return p1node;
}
else if (rt == null)
{
p1node = lt;
return p1node;
}
else
{
p2node = rt;
p1node = rt;
while (p1node.getLeft() != null)
p1node = p1node.getLeft();
p1node.setLeft(lt);
return p2node;
}
}
if (k.compareTo( root.getData())>0)
{
pnode = delete(root.getLeft(), k);
root.setLeft(pnode);
}
else
{
pnode= delete(root.getRight(), k);
root.setRight(pnode);
}
return root;
}
//countNodes function to count the nodes
public int countNodes()
{
return countNodes(root);
}
//countNodes function by passing the root
private int countNodes(BSTNode r)
{
if (r == null)
return 0;
else
{
int count = 1;
count += countNodes(r.getLeft());
count+= countNodes(r.getRight());
return count;
}
}
// search function
public boolean search(String val)
{
return search(root, val);
}
// search function to search for an element recursively
private boolean search(BSTNode r, String val)
{
boolean found = false;
while ((r != null) && !found)
{
String rval = r.getData();
if (val.compareTo(rval)>0)
r = r.getLeft();
else if (val.compareTo(rval)<0)
r = r.getRight();
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
//inorder traversal function
public void inorder()
{
inorder(root);
}
//inorder traversal function recursively
private void inorder(BSTNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
//preorder traversal function
public void preorder()
{
preorder(root);
}
//preorder traversal function recursively
private void preorder(BSTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
//preorder traversal function
public void postorder()
{
postorder(root);
}
//postorder traversal function recursively
private void postorder(BSTNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
}
import java.util.*;
public class BinaryTreeImplementation
{
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
String name[]={"Daniel", "George", "Adam", "Peter", "Michael", "Jones", "Tom", "Allison", "James","Brian"};
BSTree bstree=new BSTree();
//insert the elements
for(int i=0;i<name.length;i++)
{
bstree.insert(name[i]);
}
//call the preorder
System.out.println(" The list of names in preorder are: ");
bstree.preorder();
//call the inorder order function
System.out.println(" The list of names in inorder are: ");
bstree.inorder();
//call the post order function
System.out.println(" The list of names in postorder are: ");
bstree.postorder();
//delete Peter from the list
System.out.println(" Peter is getting deleted.");
bstree.delete("Peter");
//call the preorder
System.out.println(" The list of names in postorder after removing Peter are: ");
bstree.preorder();
//Delete Brian from the list
System.out.println(" Brian is getting deleted.");
bstree.delete("Brian");
//call the preorder
System.out.println(" The list of names in postorder after removing Brian are: ");
bstree.preorder();
}
}
Sample Output:
The list of names in preorder are:
Daniel George Peter Tom Michael Jones James Adam Allison Brian
The list of names in inorder are:
Tom Peter Michael Jones James George Daniel Brian Allison Adam
The list of names in postorder are:
Tom James Jones Michael Peter George Brian Allison Adam Daniel
Peter is getting deleted.
Peter deleted from the tree
The list of names in postorder after removing Peter are:
Daniel George Michael Tom Jones James Adam Allison Brian
Brian is getting deleted.
Brian deleted from the tree
The list of names in postorder after removing Brian are:
Daniel George Michael Tom Jones James Adam Allison
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.