CS3401 Homework Assignment 8
Homework Assignment #8
Exercise #1
Modify the DisplayBinaryTree.java class given out in Sample Code #8, to add three new buttons: "Show Inorder", "Show Preorder", and "Show Postorder". Each of these buttons when pressed must pop up a JOptionPane message dialog box that shows the values in the tree listed in the proper order for the ordering controlled by that button. For instance, if the "Show Inorder" button is pressed for the following tree:
Then a pop up dialog will show something like:
And if the user had pressed the "Show Preorder" button, a pop up dialog will show something like the following:
And if the user had pressed the "Show Postorder" button, a pop up dialog will show something like the following:
You will need the following three classes in your class hierarchy in order to get your program working (they are the same ones from the last assignment, and you should not change them at all):
- Tree.java (Interface)
- AbstractTree.java (Implments Tree)
- BinaryTree.java (Inherits from AbstractTree)
Tree.javaAbstractTree.java
package cs;
//********************************************************************
// The Tree Interface
//********************************************************************
public interface Tree<E> extends Iterable<E> {
/** Return true if the element is in the tree */
public boolean search(E e);
/** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e);
/** Delete the specified element from the tree
* Return true if the element is deleted successfully */
public boolean delete(E e);
/** Inorder traversal from the root*/
public void inorder();
/** Postorder traversal from the root */
public void postorder();
/** Preorder traversal from the root */
public void preorder();
/** Get the number of nodes in the tree */
public int getSize();
/** Return true if the tree is empty */
public boolean isEmpty();
/** Return an iterator to traverse elements in the tree */
public java.util.Iterator<E> iterator();
}
package cs;BinaryTree.java
//********************************************************************
// The AbstractTree class
//********************************************************************
public abstract class AbstractTree<E extends Comparable<E>>
implements Tree<E> {
/** Inorder traversal from the root*/
public void inorder() {
}
/** Postorder traversal from the root */
public void postorder() {
}
/** Preorder traversal from the root */
public void preorder() {
}
/** Return true if the tree is empty */
public boolean isEmpty() {
return getSize() == 0;
}
/** Return an iterator to traverse elements in the tree */
public java.util.Iterator<E> iterator() {
return null;
}
}
package cs;DisplayBinaryTree.java
//********************************************************************
// The BinaryTree class
//********************************************************************
import java.util.*;
public class BinaryTree<E extends Comparable<E>>
extends AbstractTree<E> {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BinaryTree() {
}
/** Create a binary tree from an array of objects */
public BinaryTree(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
/** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else // element matches current.element
return true; // Element is found
}
return false;
}
/** Insert element o into the binary tree
* Return true if the element is inserted successfully */
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
}
/** Inorder traversal from the root*/
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
/** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/** Inner class tree node */
public static class TreeNode<E extends Comparable<E>> {
E element;
TreeNode<E> left;
TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Returns a path from the root leading to the specified element */
public ArrayList<TreeNode<E>> path(E e) {
ArrayList<TreeNode<E>> list = new ArrayList<TreeNode<E>>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
current = current.right;
}
else
break;
}
return list; // Return an array of nodes
}
/** Delete an element from the binary tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
/** Obtain an iterator. Use inorder. */
public Iterator<E> iterator() {
return inorderIterator();
}
/** Obtain an inorder iterator */
public Iterator<E> inorderIterator() {
return new InorderIterator();
}
// Inner class InorderIterator
class InorderIterator implements Iterator<E> {
// Store the elements in a list
private ArrayList<E> list = new ArrayList<E>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root*/
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
/** Next element for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move cursor to the next */
public E next() {
return list.get(current++);
}
/** Remove the current element and refresh the list */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}
//********************************************************************
// An Application for displaying Binary Search Tree nodes
//********************************************************************
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import cs.BinaryTree.TreeNode;
public class DisplayBinaryTree extends JPanel {
private BinaryTree<Integer> tree; // A binary tree to be displayed
private JTextField jtfKey = new JTextField(5);
private TreeView view = new TreeView();
private JButton jbtInsert = new JButton("Insert");
private JButton jbtDelete = new JButton("Delete");
private JButton jbtinOrder = new JButton("Show Inorder");
private JButton jbtpOrder = new JButton("Show Preorder");
private JButton jbtpostOrder = new JButton("Show Postorder");
String output = "";
/** Construct a view for a binary tree */
public DisplayBinaryTree(BinaryTree<Integer> tree) {
this.tree = tree; // Set a binary tree to be displayed
setPreferredSize (new Dimension(800, 400));
setUI();
}
/** Initialize UI for binary tree */
private void setUI() {
this.setLayout(new BorderLayout());
add(view, BorderLayout.CENTER);
JPanel panel = new JPanel();
panel.add(new JLabel("Enter a key: "));
panel.add(jtfKey);
panel.add(jbtInsert);
panel.add(jbtDelete);
panel.add(jbtinOrder);
panel.add(jbtpOrder);
panel.add(jbtpostOrder);
add(panel, BorderLayout.SOUTH);
BinaryTree<Integer> tree2 = new BinaryTree<Integer>();
jbtInsert.addActionListener(new ActionListener() {
@Override // Process the Insert button event
public void actionPerformed(ActionEvent e) {
int key = Integer.parseInt(jtfKey.getText());
if (tree.search(key)) { // key is in the tree already
JOptionPane.showMessageDialog(null,
key + " is already in the tree");
}
else {
tree.insert(key); // Insert a new key
view.repaint(); // Redisplay the tree
}
}
});
jbtDelete.addActionListener(new ActionListener() {
@Override // Process the Delete button event
public void actionPerformed(ActionEvent e) {
int key = Integer.parseInt(jtfKey.getText());
if (!tree.search(key)) { // key is not in the tree
JOptionPane.showMessageDialog(null,
key + " is not in the tree");
}
else {
tree.delete(key); // Delete a key
view.repaint(); // Redisplay the tree
}
}
});
jbtinOrder.addActionListener(new ActionListener() {
@Override // Process the Delete button event
public void actionPerformed(ActionEvent e) {
if (tree.getSize() < 1) { // key is not in the tree
JOptionPane.showMessageDialog(null, "Its empty");
}
else {
output = "Inorder is: ";
BinaryTree.TreeNode<Integer> root = tree.getRoot();
inorder(root);
JOptionPane.showMessageDialog(null, output);
}
}
});
jbtpOrder.addActionListener(new ActionListener() {
@Override // Process the Delete button event
public void actionPerformed(ActionEvent e) {
if (tree.getSize() < 1) { // key is not in the tree
JOptionPane.showMessageDialog(null, "Its empty");
}
else {
output = "Preorder is: ";
BinaryTree.TreeNode<Integer> root = tree.getRoot();
preorder(root);
JOptionPane.showMessageDialog(null, output);
}
}
});
jbtpostOrder.addActionListener(new ActionListener() {
@Override // Process the Delete button event
public void actionPerformed(ActionEvent e) {
if (tree.getSize() < 1) { // key is not in the tree
JOptionPane.showMessageDialog(null, "Its empty");
}
else {
output = "Post order is: ";
BinaryTree.TreeNode<Integer> root = tree.getRoot();
postorder(root);
JOptionPane.showMessageDialog(null, output);
}
}
});
}
public void postorder(TreeNode<Integer> root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
output += root.element + " ";
}
public void preorder(TreeNode<Integer> root){
if (root == null) return;
output += root.element + " ";
preorder(root.left);
preorder(root.right);
}
public void inorder(TreeNode<Integer> root){
if (root == null) return;
inorder(root.left);
output += root.element + " ";
inorder(root.right);
}
// Inner class TreeView for displaying a tree on a panel
class TreeView extends JPanel {
private int radius = 20; // Tree node radius
private int vGap = 50; // Gap between two levels in a tree
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
if (tree.getRoot() != null) {
// Display tree recursively
displayTree(g, tree.getRoot(), getWidth() / 2, 30,
getWidth() / 4);
}
}
/** Display a subtree rooted at position (x, y) */
private void displayTree(Graphics g,
BinaryTree.TreeNode<Integer> root,
int x, int y, int hGap) {
// Display the root
g.drawOval(x - radius, y - radius, 2 * radius, 2 * radius);
g.drawString(root.element + "", x - 6, y + 4);
if (root.left != null) {
// Draw a line to the left node
connectTwoCircles(g, x - hGap, y + vGap, x, y);
// Draw the left subtree recursively
displayTree(g, root.left, x - hGap, y + vGap, hGap / 2);
}
if (root.right != null) {
// Draw a line to the right node
connectTwoCircles(g, x + hGap, y + vGap, x, y);
// Draw the right subtree recursively
displayTree(g, root.right, x + hGap, y + vGap, hGap / 2);
}
}
/** Connect two circles centered at (x1, y1) and (x2, y2) */
private void connectTwoCircles(Graphics g,
int x1, int y1, int x2, int y2) {
double d = Math.sqrt(vGap * vGap + (x2 - x1) * (x2 - x1));
int x11 = (int)(x1 - radius * (x1 - x2) / d);
int y11 = (int)(y1 - radius * (y1 - y2) / d);
int x21 = (int)(x2 + radius * (x1 - x2) / d);
int y21 = (int)(y2 + radius * (y1 - y2) / d);
g.drawLine(x11, y11, x21, y21);
}
}
public static void main(String[] args) {
JFrame frame = new JFrame("Display Binary Tree");
frame.add(new DisplayBinaryTree(new BinaryTree<Integer>()));
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.pack();
frame.setVisible(true);
}
}
Comments
Post a Comment