Objective: Write a program which creates a binary search tree of different fruit

Question

Objective:

Write a program which creates a binary search tree of different fruit from a file.

·     The comparison is based on the fruit’s weight

·     The file is tab delimited format goes as follows

o  Fruit Type weight

·     The binary search tree needs to have the following methods

o  insert: inserts a new fruit into the tree

o  delete: deletes the fruit instance. Keep in mind that in order for a fruit to be equal it must have the same same type and weight.

o  print pre-order traversal: Print the data. Next explore the left subtree. Finally right explore subtree.

o  print in-order traversal: Explore the left subtree. Print the data. Finally explore the right subtree.

o  print post-order traversal: Explore the left subtree. Then explore the right subtree. Finally print out the data.

·     Finally write a test file that demonstrates THE POWER OF TREES!!! FRUIT!!! By reading a shape file*.

HINTS:

Creating a class for fruit makes this problem so much easier

Having a toString, compareTo, and an equals method would really be useful

Recursion is your friend.

file* (please copy and paste the below text into a text file so that you can run the program with the appropriate results)

Explanation / Answer

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class LinkedBSTree {
private class Node
{
private float data;
private String name;
private Node leftChild;
private Node rightChild;
public Node (String aname, float aData)
{
name = aname;
data = aData;
leftChild = null;
rightChild = null;
}
}
private Node root;
public LinkedBSTree()
{
root = null;
}
public void insert(String name, float data)
{
if(root == null)
{
root = new Node(name, data);
}
else
{
insert(root, name, data);
}
}
private Node insert(Node aNode,String name, float data)
{
if(aNode == null) //found a leaf, create a new Node
{
aNode = new Node(name,data);
}
else if(data < aNode.data) //GO LEFT
{
aNode.leftChild = insert(aNode.leftChild,name,data);
}
else if(data>=aNode.data) //GO RIGHT
{
aNode.rightChild = insert(aNode.rightChild, name, data);
}
return aNode;
}
//****DELETION****\
public void delete(String name, float data)
{
delete(root, name, data);
}
private Node delete(Node aNode, String name, float data)
{
//step 1: find the value
//JJ reccomends that one uses a already existing searching method, but for notes sake we shall make our own
if(aNode ==null) //data not found
return null;
if(data<aNode.data) //GO LEFT
aNode.leftChild = delete(aNode.leftChild, name, data);
else if(data>aNode.data) //GO RIGHT
aNode.rightChild = delete(aNode.rightChild, name, data);
else //FOUND, DELETE
{
if(aNode.rightChild == null) //either no children or just left
return aNode.leftChild;
if(aNode.leftChild == null) //right child only
return aNode.rightChild;
  
//we have two children if it reaches here without going through either of the If statements
Node temp = aNode; //must have a temp container to preserve the links
//find the minimum element in the tree
aNode = findMinInTree(aNode.rightChild);
//delete the duplicate min in right subtree
aNode.rightChild = deleteMinFromTree(aNode.rightChild);
aNode.leftChild = temp.leftChild;
}
return aNode;
}
private Node findMinInTree(Node aNode)
{
if (aNode == null)
return null;
if(aNode.leftChild == null)
return aNode;
else
return findMinInTree(aNode.leftChild);
}
private Node deleteMinFromTree(Node aNode)
{
if (aNode == null)
return null;
if(aNode.leftChild==null)
return aNode;
aNode.leftChild = deleteMinFromTree(aNode.leftChild);
return aNode;
}
  
public void printPreOrder() //pre-order traversal
{
printPreOrder(root);
}
private void printPreOrder(Node aNode)
{
if(aNode ==null)
return;
//Process
System.out.println(aNode.data);
if(aNode.leftChild != null)
printPreOrder(aNode.leftChild);
if(aNode.rightChild != null)
printPreOrder(aNode.rightChild);
return;
}
  
public void printInOrder() // N order Traversal
{
printInOrder(root);
}
private void printInOrder(Node aNode)
{
if(aNode==null)
return;
if(aNode.leftChild != null)
printInOrder(aNode.leftChild);
  
System.out.println(aNode.name + " " +aNode.data); //process the node
if(aNode.rightChild != null)
printInOrder(aNode.rightChild);
return;
}

public static void main(String args[])
{
LinkedBSTree l = new LinkedBSTree();
       String fileName = "input.txt";

       try (BufferedReader br = new BufferedReader(new FileReader(fileName))) {

           String line;
           while ((line = br.readLine()) != null) {
               String[] item = line.split(" ");
l.insert(item[0], Float.parseFloat(item[1]));
           }

       } catch (IOException e) {
           e.printStackTrace();
       }
       l.printInOrder();

   }
}

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.