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):
Note that the BinaryTree.java class has inorder(), preorder() and postorder() methods, but those methods just print out the ordering to the console instead of returning the result as a string. You will need to create versions of those methods inside of your DisplayBinaryTree.java class that return the ordering as a string, so you can add the string to the message shown by your JOptionPane message dialog box.



Tree.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();
}

AbstractTree.java
package cs;
//********************************************************************
//  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;
  }
}

BinaryTree.java
package cs;
//********************************************************************
//  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;
  }
}

DisplayBinaryTree.java
//********************************************************************
//  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);
  }
}

Popular posts from this blog

CS3401 Practice Quiz 2 Part 2

CS3401 Practice Quiz 2 Part 1