SHARE
TWEET

Untitled

a guest Sep 23rd, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import org.w3c.dom.Node;
  2.  
  3. import java.awt.*;
  4. import java.awt.event.*;
  5. import javax.swing.*;
  6. import java.util.*;
  7. import java.util.Scanner;
  8. import java.io.*;
  9.  
  10. public class AVLTest extends JPanel implements ActionListener {
  11.     public static final long serialVersionUID = 3L;
  12.     /* The binary tree */
  13.     private AVLTree tree = null;
  14.  
  15.     /* The node location of the tree */
  16.     private HashMap<AVLTree.AVLTreeNode, Rectangle> nodeLocations = null;
  17.  
  18.     /* The sizes of the subtrees */
  19.     private HashMap<AVLTree.AVLTreeNode, Dimension> subtreeSizes = null;
  20.  
  21.     /* Do we need to calculate locations */
  22.     static private boolean dirty = true;
  23.  
  24.     /* Space between nodes */
  25.     private int parent2child = 20, child2child = 30;
  26.  
  27.     /* Helpers */
  28.     private Dimension empty = new Dimension(0, 0);
  29.  
  30.     private FontMetrics fm = null;
  31.  
  32.     public AVLTest(AVLTree tree) {
  33.         this.tree = tree;
  34.         nodeLocations = new HashMap<AVLTree.AVLTreeNode, Rectangle>();
  35.         subtreeSizes = new HashMap<AVLTree.AVLTreeNode, Dimension>();
  36.     }
  37.  
  38.     public void actionPerformed(ActionEvent e) {
  39.         repaint();
  40.     }
  41.  
  42.     // calculate node locations
  43.     private void calculateLocations() {
  44.         nodeLocations.clear();
  45.         subtreeSizes.clear();
  46.         AVLTree.AVLTreeNode root = tree.getRoot();
  47.         if (root != null) {
  48.             calculateSubtreeSize(root);
  49.             calculateLocation(root, Integer.MAX_VALUE, Integer.MAX_VALUE, 0);
  50.         }
  51.     }
  52.  
  53.     // calculate the size of a subtree rooted at n
  54.     private Dimension calculateSubtreeSize(AVLTree.AVLTreeNode n) {
  55.         if (n == null)
  56.             return new Dimension(0, 0);
  57.         Dimension ld = calculateSubtreeSize(n.getLeft());
  58.         Dimension rd = calculateSubtreeSize(n.getRight());
  59.         int h = fm.getHeight() + parent2child + Math.max(ld.height, rd.height);
  60.         int w = ld.width + child2child + rd.width;
  61.         Dimension d = new Dimension(w, h);
  62.         subtreeSizes.put(n, d);
  63.         return d;
  64.     }
  65.  
  66.     // calculate the location of the nodes in the subtree rooted at n
  67.     private void calculateLocation(AVLTree.AVLTreeNode n, int left, int right, int top) {
  68.         if (n == null)
  69.             return;
  70.         Dimension ld = (Dimension) subtreeSizes.get(n.getLeft());
  71.         if (ld == null)
  72.             ld = empty;
  73.         Dimension rd = (Dimension) subtreeSizes.get(n.getRight());
  74.         if (rd == null)
  75.             rd = empty;
  76.         int center = 0;
  77.         if (right != Integer.MAX_VALUE)
  78.             center = right - rd.width - child2child / 2;
  79.         else if (left != Integer.MAX_VALUE)
  80.             center = left + ld.width + child2child / 2;
  81.         int width = fm.stringWidth("" + n.getElement());
  82.         Rectangle r = new Rectangle(center - width / 2 - 3, top, width + 6, fm
  83.                 .getHeight());
  84.         nodeLocations.put(n, r);
  85.         calculateLocation(n.getLeft(), Integer.MAX_VALUE, center - child2child / 2,
  86.                 top + fm.getHeight() + parent2child);
  87.         calculateLocation(n.getRight(), center + child2child / 2, Integer.MAX_VALUE,
  88.                 top + fm.getHeight() + parent2child);
  89.     }
  90.  
  91.     // draw the tree using the pre-calculated locations
  92.     private void drawTree(Graphics2D g, AVLTree.AVLTreeNode n, int px, int py, int yoffs) {
  93.         if (n == null)
  94.             return;
  95.         Rectangle r = (Rectangle) nodeLocations.get(n);
  96.         g.draw(r);
  97.         g.drawString("" + n.getElement(), r.x + 3, r.y + yoffs);
  98.         if (px != Integer.MAX_VALUE)
  99.             g.drawLine(px, py, r.x + r.width / 2, r.y);
  100.         drawTree(g, n.getLeft(), r.x + r.width / 2, r.y + r.height, yoffs);
  101.         drawTree(g, n.getRight(), r.x + r.width / 2, r.y + r.height, yoffs);
  102.     }
  103.  
  104.     public void paint(Graphics g) {
  105.         super.paint(g);
  106.         fm = g.getFontMetrics();
  107.         // if node locations not calculated
  108.         if (dirty) {
  109.             calculateLocations();
  110.             dirty = false;
  111.         }
  112.         Graphics2D g2d = (Graphics2D) g;
  113.         g2d.translate(getWidth() / 2, parent2child);
  114.         drawTree(g2d, tree.getRoot(), Integer.MAX_VALUE, Integer.MAX_VALUE, fm
  115.                 .getLeading()
  116.                 + fm.getAscent());
  117.         fm = null;
  118.     }
  119.  
  120.     static void printMenu() {
  121.         final String newline = System.getProperty("line.separator");
  122.  
  123.         String strMenu = "+--- Binary trees ---" + newline;
  124.         strMenu += "r : Reset tree" + newline;
  125.         strMenu += "i : Insert key" + newline;
  126.         strMenu += "f : Find key" + newline;
  127.         strMenu += "d : Delete key" + newline;
  128.         strMenu += "h : Height of key" + newline;
  129.         strMenu += "q : Quit program" + newline;
  130.         strMenu += "x : show this text" + newline;
  131.         System.out.print(strMenu);
  132.     }
  133.  
  134.     static char getChar(Scanner in) {
  135.         String tmp;
  136.  
  137.         do {
  138.             tmp = in.nextLine();
  139.         } while (tmp.length() != 1);
  140.  
  141.         return tmp.charAt(0);
  142.     }
  143.  
  144.     static int getInt(Scanner in) {
  145.         int tmp;
  146.  
  147.         while (!in.hasNextInt()) {
  148.             in.nextLine();
  149.         }
  150.  
  151.         tmp = in.nextInt();
  152.         in.nextLine();
  153.  
  154.         return tmp;
  155.     }
  156.  
  157.     static String getString(Scanner in) {
  158.         return in.nextLine();
  159.     }
  160.  
  161.     /**
  162.      * Fetch the entire contents of a text file, and return it in a String.
  163.      */
  164.     static public String getContents(File aFile) {
  165.  
  166.         StringBuilder contents = new StringBuilder();
  167.  
  168.         try {
  169.             // use buffering, reading one line at a time
  170.  
  171.             BufferedReader input = new BufferedReader(new FileReader(aFile));
  172.             try {
  173.                 String line = null; // not declared within while loop
  174.  
  175.                 while ((line = input.readLine()) != null) {
  176.                     contents.append(line);
  177.                     contents.append(System.getProperty("line.separator"));
  178.                 }
  179.             } finally {
  180.                 input.close();
  181.             }
  182.         } catch (IOException ex) {
  183.             ex.printStackTrace();
  184.         }
  185.  
  186.         return contents.toString();
  187.     }
  188.  
  189.     public static void main(String[] args) {
  190.         if (args.length != 0) { // check command line flags
  191.  
  192.             System.out.println("Usage: java AVLTest ");
  193.  
  194.         } else { // no flag
  195.             AVLTree<Integer> tree = new AVLTree<>();
  196.  
  197.             JFrame f = new JFrame("BST");
  198.             f.getContentPane().add(new AVLTest(tree));
  199.             // create and add an event handler for window closing event
  200.             f.addWindowListener(new WindowAdapter() {
  201.                 public void windowClosing(WindowEvent e) {
  202.                     System.exit(0);
  203.                 }
  204.             });
  205.             f.setBounds(50, 50, 600, 400);
  206.             f.setVisible(true);
  207.  
  208.             char c;
  209.             int k;
  210.             String v;
  211.             Scanner in = new Scanner(System.in);
  212.             printMenu();
  213.             for (;;) {
  214.                 System.out.print("lab > ");
  215.                 System.out.flush();
  216.                 c = getChar(in);
  217.  
  218.                 switch (c) {
  219.                     case 'r':
  220.                         tree = new AVLTree<>();
  221.                         f.dispose();
  222.                         f = new JFrame("BST");
  223.                         f.getContentPane().add(new AVLTest(tree));
  224.                         // create and add an event handler for window closing event
  225.                         f.addWindowListener(new WindowAdapter() {
  226.                             public void windowClosing(WindowEvent e) {
  227.                                 System.exit(0);
  228.                             }
  229.                         });
  230.                         f.setBounds(50, 50, 600, 400);
  231.                         f.setVisible(true);
  232.                         break;
  233.                     case 'h':
  234.                         System.out.println("Height of key (int): ");
  235.                         System.out.flush();
  236.                         k = getInt(in);
  237.                         System.out.println("The node: " + k + " has the height: " + tree.getNodeHeight(k));
  238.                         break;
  239.                     case 'i':
  240.                         System.out.print("Insert key (int): ");
  241.                         System.out.flush();
  242.                         k = getInt(in);
  243.                         tree.insert(k);
  244.                         System.out
  245.                                 .print("Inserted key=" + k + "\n");
  246.                         System.out.flush();
  247.                         dirty = true;
  248.                         f.repaint();
  249.                         break;
  250.                     case 'd':
  251.                         System.out.print("Delete key (int): ");
  252.                         System.out.flush();
  253.                         k = getInt(in);
  254.                         tree.remove(k);
  255.                         dirty = true;
  256.                         f.repaint();
  257.                         break;
  258.                     case 'f':
  259.                         System.out.print("Find key (int): ");
  260.                         System.out.flush();
  261.                         k = getInt(in);
  262.                         Integer str = tree.find(k);
  263.                         if (str != null)
  264.                             System.out.print("Found key:" + k + "\n");
  265.                         else
  266.                             System.out.print("Key:" + k + " not found\n");
  267.                         break;
  268.                     case 'q':
  269.                         System.out.println("Program terminated.");
  270.                         System.exit(0);
  271.                         break;
  272.                     case 'x':
  273.                         printMenu();
  274.                         break;
  275.                     default:
  276.                         System.out.print("**** Sorry, No menu item named '");
  277.                         System.out.print(c + "'\n");
  278.                         System.out.flush();
  279.                 }
  280.             }
  281.         }
  282.     }
  283. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top