Homework SourseDear Experts topic Binary Search Tree BST Please help on bel
Dear Experts,
topic Binary Search Tree (BST). Please help on below request urgently. Thanks
Coding provided. Please help mofidy based on question requirement. Question is :
In this assignment, you will have to implement the basic functions needed to build and search binary search trees (abbreviated BST) as given in example Tree.java.
Your implementation should be such that the nodes of the tree contain an integer and links (possibly null) to the left and right children of the node.
You are required to do the following.
Develop GUI of the program based on the example given you in class named Tree.java to
1. Create the BST where the data value at each node is an integer and constructed dynamically based on the end user.
2. Show the BST after the random insertions have been done by the end user in the tree of part 1.
3. Draw the tree after deletions of one of the existing node.
4. Display an option on the GUI screen for the traversal order procedures to be performed on the BST as the following:
a) In order.
b) Postorder.
c) Preorder
5) Display an option to show the height of the tree
Based on below Coding please modify as requested in question.
package tree;
/**
*
*
*/
// tree.java
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
class Node
{
public int iData; // data item (key)
public double dData; // data item
public Node leftChild; // this node\'s left child
public Node rightChild; // this node\'s right child
public void displayNode() // display ourself
{
System.out.print(\'{\');
System.out.print(iData);
System.out.print(\", \");
System.out.print(dData);
System.out.print(\"} \");
}
} // end class Node
////////////////////////////////////////////////////////////////
class Tree
{
private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
// -------------------------------------------------------------
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn\'t find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id, double dd)
{
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn\'t find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null&&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current\'s left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child\'s left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print(\"\ Preorder traversal: \");
preOrder(root);
break;
case 2: System.out.print(\"\ Inorder traversal: \");
inOrder(root);
break;
case 3: System.out.print(\"\ Postorder traversal: \");
postOrder(root);
break;
}
System.out.println();
}
// -------------------------------------------------------------
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
System.out.print(localRoot.iData + \" \");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + \" \");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + \" \");
}
}
// -------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
\"......................................................\");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
System.out.print(\' \');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print(\"--\");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
System.out.print(\' \');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // end while isRowEmpty is false
System.out.println(
\"......................................................\");
} // end displayTree()
// -------------------------------------------------------------
} // end class Tree
////////////////////////////////////////////////////////////////
class TreeApp
{
public static void main(String[] args) throws IOException
{
int value;
Tree theTree = new Tree();
theTree.insert(50, 1.5);
theTree.insert(25, 1.2);
theTree.insert(75, 1.7);
theTree.insert(12, 1.5);
theTree.insert(37, 1.2);
theTree.insert(43, 1.7);
theTree.insert(30, 1.5);
theTree.insert(33, 1.2);
theTree.insert(87, 1.7);
theTree.insert(93, 1.5);
theTree.insert(97, 1.5);
while(true)
{
System.out.print(\"Enter first letter of show, \");
System.out.print(\"insert, find, delete, or traverse: \");
int choice = getChar();
switch(choice)
{
case \'s\':
theTree.displayTree();
break;
case \'i\':
System.out.print(\"Enter value to insert: \");
value = getInt();
theTree.insert(value, value + 0.9);
break;
case \'f\':
System.out.print(\"Enter value to find: \");
value = getInt();
Node found = theTree.find(value);
if(found != null)
{
System.out.print(\"Found: \");
found.displayNode();
System.out.print(\"\ \");
}
else
System.out.print(\"Could not find \");
System.out.print(value + \'\ \');
break;
case \'d\':
System.out.print(\"Enter value to delete: \");
value = getInt();
boolean didDelete = theTree.delete(value);
if(didDelete)
System.out.print(\"Deleted \" + value + \'\ \');
else
System.out.print(\"Could not delete \");
System.out.print(value + \'\ \');
break;
case \'t\':
System.out.print(\"Enter type 1, 2 or 3: \");
value = getInt();
theTree.traverse(value);
break;
default:
System.out.print(\"Invalid entry\ \");
} // end switch
} // end while
} // end main()
// -------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
// -------------------------------------------------------------
} // end class TreeApp
////////////////////////////////////////////////////////////////
}
Solution
package binarysearchtreegui;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.awt.Component;
import java.io.File;
import java.util.HashMap;
public class BinarySearchTreeGUI extends JPanel {
BinarySearchTree myBST = new BinarySearchTree();
static Graphics g;
private HashMap nodeLocations = null;
private HashMap subtreeSizes = null;
String value = \"sadf\";
int traversalType, in_Order, pre_Order, post_Order;
private Dimension empty = new Dimension(0, 0);
private FontMetrics fm = null;
private boolean dirty = true;
public BinarySearchTreeGUI() {
setBorder(BorderFactory.createLineBorder(Color.black));
nodeLocations = new HashMap();
subtreeSizes = new HashMap();
}
public static void main(String args[]) {
Runnable r;
r = new Runnable() {
public void run() {
BinarySearchTreeGUI demo;
demo = new BinarySearchTreeGUI();
demo.startGUI();
demo.repaint();
}
};
SwingUtilities.invokeLater(r);
}
public void startGUI() {
setInsert();
JFrame frame;
JPanel buttonPanel, statusPanel;
JLabel label, status;
JButton clear, add, delete, find;
JMenuBar menubar;
JMenu file, traversal, help;
JMenuItem save, exit, inOrder, preOrder, postOrder, helpContents;
JScrollPane scrollPane;
final JTextField input;
final TreePanel tree = new TreePanel();
final BinarySearchTree bst = new BinarySearchTree();
frame = new JFrame();
frame.setTitle(\"A Graphical User Interface for Binary Search Tree Visulisation\");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setLayout(new BorderLayout());
menubar = new JMenuBar();
frame.setJMenuBar(menubar);
file = new JMenu();
file.setText(\"File\");
file.setMnemonic(KeyEvent.VK_F);
menubar.add(file);
save = new JMenuItem();
save.setText(\"Save\");
save.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
saveFileChooser();
}
});
file.add(save);
exit = new JMenuItem();
exit.setText(\"Exit\");
exit.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
exit();
}
});
file.add(exit);
traversal = new JMenu();
traversal.setText(\"Traversal\");
traversal.setMnemonic(KeyEvent.VK_T);
menubar.add(traversal);
inOrder = new JMenuItem();
inOrder.setText(\"In-Order\");
inOrder.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
in_Order = 1;
traversalType = in_Order;
System.out.println(\"traversal = \" + traversalType);
}
});
traversal.add(inOrder);
postOrder = new JMenuItem();
postOrder.setText(\"Post-Order\");
postOrder.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
post_Order = 2;
traversalType = post_Order;
System.out.println(\"traversal = \" + traversalType);
}
});
traversal.add(postOrder);
preOrder = new JMenuItem();
preOrder.setText(\"Pre-Order\");
preOrder.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
pre_Order = 3;
traversalType = pre_Order;
System.out.println(\"traversal = \" + traversalType);
}
});
traversal.add(preOrder);
help = new JMenu();
help.setText(\"Help\");
help.setMnemonic(KeyEvent.VK_H);
menubar.add(help);
helpContents = new JMenuItem();
helpContents.setText(\"Help Contents\");
helpContents.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
helpMenu();
}
});
help.add(helpContents);
scrollPane = new JScrollPane(tree, JScrollPane.VERTICAL_SCROLLBAR_ALWAYS, JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);
frame.add(scrollPane, BorderLayout.CENTER);
buttonPanel = new JPanel();
buttonPanel.setLayout(new FlowLayout());
frame.add(buttonPanel, BorderLayout.NORTH);
input = new JTextField(5);
buttonPanel.add(input);
clear = new JButton();
clear.setText(\"Clear\");
clear.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
//bst.nodeValue(value);
}
});
buttonPanel.add(clear);
add = new JButton();
add.setText(\"Add...\");
add.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
String root;
if (!\"\".equals(value) && value != null) {
tree.setNode(value);
setInsert();
tree.repaint();
}
System.out.println(myBST.getRootNode());
System.out.println(\"Value \" + value);
}
});
buttonPanel.add(add);
find = new JButton();
find.setText(\"Find...\");
find.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
}
});
buttonPanel.add(find);
delete = new JButton();
delete.setText(\"Delete...\");
delete.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
}
});
buttonPanel.add(delete);
statusPanel = new JPanel();
statusPanel.setLayout(new FlowLayout());
frame.add(statusPanel, BorderLayout.SOUTH);
label = new JLabel();
label.setText(\"Status\");
label.setHorizontalAlignment(JLabel.LEFT);
statusPanel.add(label);
status = new JLabel();
status.setBackground(Color.white);
statusPanel.add(status);
frame.setSize(500, 550);
frame.setVisible(true);
}
public void helpMenu() {
System.out.println(\"Help pressed\");
Object help = (\" Help Information\");
JOptionPane.showMessageDialog(null, help);
}
public void exit() {
System.out.println(\"Quit pressed\");
System.exit(0);
}
public void saveFileChooser() {
String selectedFileSave;
String contents;
contents = getText();
JFileChooser fileSave = new JFileChooser(System.getProperty(\"user.dir\", \"user.home\"));
int return_fileOpen = fileSave.showSaveDialog(null);
if (return_fileOpen == JFileChooser.APPROVE_OPTION) {
selectedFileSave = fileSave.getSelectedFile().getName();
System.out.println(\"Selected file for save is \" + selectedFileSave);
try {
PrintWriter out = new PrintWriter(selectedFileSave);
out.println(contents);
out.println(\"The root node of the BST: \" + myBST.getRootNode());
out.println(\"The height of the BST: \" + myBST.getTreeHeight());
out.println(\"The number of nodes in the BST: \" + myBST.count());
out.println(\"The contents of the BST: \" + myBST.toString());
out.close();
} catch (IOException e) {
System.out.println(\"Uh oh\");
}
}
System.out.println(\"SaveMenuItem pressed\");
}
public String getText() {
return value;
}
public void setInsert() {
myBST.insert(value);
}
BinaryTreeNode node;
BinaryTreeNode nodes[];
int levels[] = {5, 10, 30, 20, 10};
int index = 0;
int level = 0;
String data;
String root;
public void nodeValue(BinaryTreeNode node) {
node = myBST.getRootNode();
if (node != null) {
node.getLeftNode();
index++;
nodes[index] = node;
node.getRightNode();
}
System.out.println(\"TreePanel \" + node);
}
}
