Binary Search Tree

GUI Version

By: Nicholas Duchon.

Outline:

Previous Page:


Notes:

See the previous for some general notes about this page.

Text Output

X:
                        /1
                             \2
                                  \3
                                       \4
                   /5
                                       /6
                                  /7
                             /8
                        \9
              /10
                        /11
                             \12
                                  \13
                   \15
         /20
                   /25
              \30
                   \35
    >40
                   /45
              /50
                   \55
         \60
                   /65
              \70
                   \75

X in-order:
1 2 3 4 5 6 7 8 9 10 11 12 13 15 20 25 30 35 40 45 50 55 60 65 70 75
X pre-order:
40 20 10 5 1 2 3 4 9 8 7 6 15 11 12 13 30 25 35 60 50 45 55 70 65 75
X post-order:
4 3 2 1 6 7 8 9 5 13 12 11 15 10 25 35 30 20 45 55 50 65 75 70 60 40
X level-order:
40 20 60 10 30 50 70 5 15 25 35 45 55 65 75 1 9 11 2 8 12 3 7 13 4 6
find: 10
find: 20
Size: 26
MAX: 75
Removing: 10
result:
                        /1
                             \2
                                  \3
                                       \4
                   /5
                                  /6
                             /7
                        \8
              /9
                        /11
                             \12
                                  \13
                   \15
         /20
                   /25
              \30
                   \35
    >40
                   /45
              /50
                   \55
         \60
                   /65
              \70
                   \75
Removing: 10 5
result:
                        /1
                             \2
                                  \3
                   /4
                                  /6
                             /7
                        \8
              /9
                        /11
                             \12
                                  \13
                   \15
         /20
                   /25
              \30
                   \35
    >40
                   /45
              /50
                   \55
         \60
                   /65
              \70
                   \75

Removing: 10 5 3
result:
                        /1
                             \2
                   /4
                                  /6
                             /7
                        \8
              /9
                        /11
                             \12
                                  \13
                   \15
         /20
                   /25
              \30
                   \35
    >40
                   /45
              /50
                   \55
         \60
                   /65
              \70
                   \75

Removing: 10 5 3 40
result:
                        /1
                             \2
                   /4
                                  /6
                             /7
                        \8
              /9
                        /11
                             \12
                                  \13
                   \15
         /20
                   /25
              \30
    >35
                   /45
              /50
                   \55
         \60
                   /65
              \70
                   \75

X:
                        /1
                             \2
                   /4
                                  /6
                             /7
                        \8
              /9
                        /11
                             \12
                                  \13
                   \15
         /20
                   /25
              \30
    >35
                   /45
              /50
                   \55
         \60
                   /65
              \70
                   \75


Example using strings:
                   /eight
              /five
         /four
              \nine
    >one
                        /seven
                   /six
                        \ten
              /three
         \two

enter integer values, q to quit:
q
...Bye



Code: BinarySearchTreeND_C.java

// File  : BinarySearchTreeND_C.java
// Author: Nicholas Duchon
// Date  : Sep 5, 2018
// updates:
//        Sep  3, 2018 - renamed to version C
//        Nov 16, 2008
//        Nov 22, 2008
//        Apr 17, 2009 - fixed toTreeString
//        Apr 17, 2009 - added parents to nodes and \ and / to tree display.
//        Mar 18, 2012 - cleaned up some generic lint stuff in BSTNodeND declarations
//        May 13, 2012 - toTreeString - removed use of parent reference, added label parameter
//
// Simplified, linked version of a binary search tree
// uses generic class implementing Comparable
// no exceptions thrown
//   static fields
//       all associated with toString displays
//       .. DEPTHDELTA - used to present a tree-like display using spacing
//   This code implements the following public methods
//            T is a Comparable class
//       insert   (T)  : void
//       find     (T)  : T
//       max      ()   : T
//       getSize  ()   : int
//       remove   (T)  : void
//       toString ()   : String // to tree string
//
//    private mutator/accessor methods
//       insertValue (T, BSTNodeND < T >): void - uses comparator from T
//       findValue   (T, BSTNodeND < T >): T - finds an T, returns null if not found
//       findMax                       (): T - returns max value in this subtree
//       getSize        (BSTNodeND < T >): int
//       removeRoot     (BSTNodeND < T >): BSTNodeND < T >
//       remove      (T, BSTNodeND < T >): BSTNodeND < T >
//
//    private toString methods
//       toString            (BSTNodeND) : uses toTreeString (int) to create a tree-like display
//       toInOrderString     (BSTNodeND) : recursive in-order string
//       toPreOrderString    (BSTNodeND) : recursive pre-order string
//       toPostOrderString   (BSTNodeND) : recursive post-order string
//       toLevelOrderString  (BSTNodeND) : level-order string, uses a queue (ArrayDeque)
//       toTreeString        (int, BSTNodeND, char) : recursive in-order traversal with depth offsets and parent indicators
//
// Inside the BSTNodeND class:
//    Instace fields:
//       data  < L >   generic parameter of the BSTNodeND class, NOT the BinarySearchTreeND_C class
//       BSTNodeND left, right, parent - links to create the tree
//    constructors
//       < L > generic parameterized constructor, left and right are null
//       < L >, NSTNodeND - links to parent also, for tree display
//
//    import java.util.ArrayDeque;

   import java.util.Scanner;
   import java.util.List;
   import java.util.ArrayList;

   public class BinarySearchTreeND_C
      < K extends Comparable < ? super K > >
      // ANY class that extends the base comparable type (K)
      // of this data structure instance may be inserted
   {
      static final int DEPTHDELTA = 5; // used to create a text tree display
  
      BSTNodeND < K > root = null;
  
      public void insert (K d) {
         insertNode (new BSTNodeND < K > (d));
     
} // end insert, public version
     
      public void insertNode (BSTNodeND < K > n) {
         if (root == null) root = n;
         else insertNode (n, root);
     
} // end insert Node
  
      public K find (K d) {
         if (root == null)
            return null;
         BSTNodeND < K > t = findValue (d, root);
         return (t==null)?null:t.data;
     
} // end find method
     
      public K max () {
         if (root == null)
            return null;
         return findMax(root).data;
     
} // end max method
  
      public int getSize () {
         return getSize (root);
     
}
  
      public void remove (K d) {
         root = remove (d, root);
     
} // end remove data
     
      public void drawTree (String st) {
         if (root == null)
            return;
         try { // make sure tree frame is drawn on current version of the tree
           new MyDrawTreeFrame (root, st);
           Thread.sleep (500);
         } catch (InterruptedException e) {}
     
} // end drawTree
  
      public String toString () {
         if (root == null)
            return null;
         return toString(root);
      
}
        
      private void insertNode (BSTNodeND < K > d, BSTNodeND < K > n) {
         d.parent = n;
         if (d.data.compareTo (n.data) == 0) return; // do not allow duplicates
         else if (d.data.compareTo (n.data)  > 0)
            if (n.right == null) n.right = d;
            else insertNode (d, n.right);
         else
            if (n.left == null) n.left = d;
            else insertNode (d, n.left);
     
} // end method insertNode
     
      private BSTNodeND < K > findValue (K d, BSTNodeND < K > n) {
         if (n.data.compareTo(d) == 0)
            return n;
         if (n.data.compareTo (d) > 0)
            return (n.left==null)?null:findValue (d, n.left);
         return (n.right == null)?null:findValue(d, n.right);
     
} // end findValue
     
      private BSTNodeND < K > findMax (BSTNodeND < K > n) {
         if (n.right == null)
            return n;
         return findMax(n.right);
     
} // end findValue
     
      private int getSize (BSTNodeND < K > t) {
         if (t == null)
            return 0;
         return getSize (t.left) + getSize (t.right) + 1;
     
} // end getSize node
     
      private BSTNodeND < K > removeRoot (BSTNodeND < K > t) {
         if (t.left  == null) {
            if (t.right != null)
               t.right.parent = t.parent;
            return t.right;
         }
         if (t.right == null) {
            t.left.parent = t.parent; // t.left != null because of earlier if test case
            return t.left;
         }
         BSTNodeND < K > newTop = findMax(t.left);
         remove (newTop.data, t); // lose the node instance, leave tree intact
         t.data = newTop.data;    // just replace the data at the internal node
         return t;
     
} // end remove data, tree
  
      private BSTNodeND < K > remove (K d, BSTNodeND < K > t) {
         if (t == null)
            return null;
         if (d.compareTo (t.data) < 0)
            t.left  = remove (d, t.left );
         else
            if (d.compareTo (t.data)> 0)
               t.right = remove (d, t.right);
            else // d equals t.data
               t = removeRoot (t);
         return t;
     
} // end remove data, tree
  
      private String toString (BSTNodeND < K > n) {
         return toTreeString (5, n, '>');
     
} // end toString
     
      // removed use of parent reference, added label parameter, 5/13/2012
      private String toTreeString (int depth, BSTNodeND < K > n, char label) { // depth = 0 is bad
         return
            ((n.left  == null)?"":toTreeString  (depth + DEPTHDELTA, n.left, '/'))
            + String.format ("%" + depth + "s%s\n", label, n) // ND: fixed 4/17/2009
            + ((n.right == null)?"":toTreeString (depth + DEPTHDELTA, n.right, '\\'));
      } // end method toTreeString
        
      private String toInOrderString (BSTNodeND < K > n) {
         return
              ((n.left  == null)?"":toInOrderString(n.left ))
            +  n + " "
            + ((n.right == null)?"":toInOrderString(n.right));
     
} // end toInOrderString
        
      private String toPreOrderString (BSTNodeND < K > n) {
         return
             n + " "
            + ((n.left  == null)?"":toPreOrderString(n.left ))
            + ((n.right == null)?"":toPreOrderString(n.right));
     
} // end toPreOrderString
        
      private String toPostOrderString (BSTNodeND < K > n) {
         return
              ((n.left  == null)?"":toPostOrderString(n.left ))
            + ((n.right == null)?"":toPostOrderString(n.right))
            + n + " ";
     
} // end to PostOrderString
        
         // See: http://en.wikipedia.org/wiki/Tree_traversal
      private String toLevelOrderString (BSTNodeND < K > n) {
         String st = "";
         BSTNodeND < K > node;
         java.util.ArrayDeque < BSTNodeND < K > > q
               = new java.util.ArrayDeque < BSTNodeND < K > > ();
         q.add (n);          // start queue by adding this (root?) to queue
         while (q.size() > 0) {
            node = q.remove();                          // remove the head of queue
            st += (node.data + " ");                // process head data to String
            if (node.left != null) q.add (node.left);   // insert left child at end of queue
            if (node.right != null) q.add (node.right); // insert right child at end or queue
         } // end queue processing
         return st.toString();
     
} // end to LevelOrderString
        
      // main and example methods follow
      public static void main (String args []) {
         integerExample ();
         stringExample ();
         Scanner st = new Scanner (System.in);
         while (menu(st));
         System.out.println ("...Bye");
      }
// end main
  
      static boolean menu (Scanner st) {
         System.out.println ("enter integer or String values, q to quit:");
         String line = st.nextLine();
     
   if (line.length() == 0)
        
   return true; // just <cr> causes crash on next line
  
         // allow comma+space separators
  
       Scanner tokens = new Scanner (line).useDelimiter ("[,\\s]+");
     
    if (!tokens.hasNextInt()) { // input taken as String
        
    if (!tokens.hasNext())
               return true;
        
   String sk = tokens.next();
        
   if (sk.equalsIgnoreCase ("q"))
           
   return false;
        
   BinarySearchTreeND_C <String> tree = new BinarySearchTreeND_C <String> ();
        
   tree.insert (sk);
        
   while (tokens.hasNext()) tree.insert (tokens.next());
        
   tree.drawTree ("Inserted: " + line);
        
   System.out.println ("Tree:\n   " + tree);
        
   System.out.println ("Tree in-order:\n   "    + tree.toInOrderString   (tree.root));
        
   System.out.println ("Tree pre-order:\n   "   + tree.toPreOrderString  (tree.root));
        
   System.out.println ("Tree post-order:\n   "  + tree.toPostOrderString (tree.root));
        
   System.out.println ("Tree level-order:\n   " + tree.toLevelOrderString(tree.root));
     
   } else {
        
   BinarySearchTreeND_C <Integer> tree = new BinarySearchTreeND_C <Integer> ();
        
   while (tokens.hasNextInt()) tree.insert (tokens.nextInt());
        
   tree.drawTree ("Inserted: " + line);
        
    System.out.println ("Tree:\n   " + tree);
        
   System.out.println ("Tree in-order:\n   "    + tree.toInOrderString   (tree.root));
        
   System.out.println ("Tree pre-order:\n   "   + tree.toPreOrderString  (tree.root));
        
   System.out.println ("Tree post-order:\n   "  + tree.toPostOrderString (tree.root));
        
   System.out.println ("Tree level-order:\n   " + tree.toLevelOrderString(tree.root));
     
   } // end String vs integer input string
  
     
   if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q"))
        
   return false;
  
     
   return true;
      } // e
nd menu
     
      public static void integerExample () {
         BinarySearchTreeND_C < Integer > x = new BinarySearchTreeND_C < Integer > ();
         int arr [] = {
                       40, 20, 60, 10, 30, 50, 70, 5, 15, 25, 35, 45, 55, 65, 75,
                       60, 45, 50, 40, 55,
                       1, 2, 3, 4, 5, 9, 8, 7, 6, 10, 11, 12, 13
                      };
         int rem [] = {10, 5, 3, 40};
         for (int y: arr) x.insert (y);
     
         System.out.println ("X:\n" + x);
         x.drawTree ("original");
         System.out.println ("X in-order:\n"    + x.toInOrderString(x.root));
         System.out.println ("X pre-order:\n"   + x.toPreOrderString(x.root));
         System.out.println ("X post-order:\n"  + x.toPostOrderString(x.root));
         System.out.println ("X level-order:\n" + x.toLevelOrderString(x.root));
     
         Integer t = x.find(10);
         System.out.println ("find: " + t);
         System.out.println ("find: " + x.find(20));
         System.out.println ("Size: " + x.getSize());
         System.out.println ("MAX: " + x.max());
         String st = "Removing:";
         for (int y: rem) {
            x.remove (y);
            st += " " + y;
            System.out.println (st);
            x.drawTree (st);
            System.out.println ("result:\n" + x);
         }
         System.out.println ("X:\n"  + x);
     
} // end integerExample
      
      public static void stringExample () {
         // The following is an example using a user-defined class, see below
         // notice the use of the generic parameter Example
         String [] sa = {"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"};
         BinarySearchTreeND_C < Example > ex = new BinarySearchTreeND_C < Example > ();
         for (String s: sa) ex.insert (new Example (s));
         ex.drawTree ("Example using Strings");
         System.out.println ("Example using strings: \n" + ex);
     
} // end stringExample
  
   // needs to be internal class so, eg, AVLNode in AVLND can extend this internal node class
      class BSTNodeND < L extends Comparable< ? super L > > implements MyTreeIF {
         L data;
         BSTNodeND < L > left, right, parent;
     
         BSTNodeND (L d)                  {
            data = d;
}
         BSTNodeND (L d, BSTNodeND <L> p) {
            data = d; parent = p;
}
        
         public List <MyTreeIF>
getChildren () { // MyTreeIF
            ArrayList <MyTreeIF> a = new ArrayList <MyTreeIF> ();
            if (left == null && right == null)
               return a;
            if (left == null) a.add (new BSTNodeND <String> ("*"));
            else a.add (left);
            if (right == null) a.add (new BSTNodeND <String> ("*"));
            else a.add (right);
            return a;
        
} // MyTreeIF method

         public String toString () {
            return data.toString();} // end toString method
      } /
/ end class BSTNodeND
  
  
} // end class BinarySearchTreeND_C

// A class that can be used with the BinarySearchTreeND_C data structure
// Notice the use of the generic parameter Example
   class Example implements Comparable < Example > {
      String data;
   
      public Example (String d) {
         data = d;
}
   
   // you, of course, will want a more interesting compareTo method
      public int compareTo (Example e) {
         return data.compareTo (e.data);
     
} // end compareTo method
     
      public String toString () {
         return data;
     
} // end toString
  
  
} // end class Example


Code: MyDrawTreeFrame.java

//File: MyDrawTreeFrame.java
//Author: Nicholas  Duchon
//Date:   4/9/03, updated Nov 1, 2012
// History:
//    Feb 19, 2013 - remove SVG stuff, not as helpful as I would have liked and a pain to send around
//Problem:  A frame to show a graphic display of a tree structure.
// Notes:
//   a. To use this class, create a tree node class that implements the MyTreeIF interface.
//   b. Create and/or edit a tree of nodes which implement that interface.
//   c. Instantiate the class MyDrawTreeFrame, passing the root node as the parameter.
//   d. See the code in TestTree.java for an example of how to use this class.
//   e. This class will use different fonts, different font sizes.
//   f. For an example of using this code, see the associated file TestTree.java
//   g. This code will also support:
//         1. Copying the display to the system clipboard (copy/paste).
//         2. Printing the display on a printer.
//         3. Creating an SVG (scalable vector graphics) file.
//            Uses internet files from w3.org
//   h. Uses JButton as the primary node display elements.
//   i. MyLine extends JComponent to take advantage of JComponent drawing defaults.
//   j. Classes and methods:
//         > MyDrawTreeFrame
//              - MyDrawTreeFrame (MyTreeIF)
//              - MyDrawTreeFrame (MyTreeIF, String) // display frame lable
//              - MyDrawTreeFrame (MyTreeIF, String, boolean) // closeOnExit?
//              - setupDisplay (MyTreeIF, String)
//              - paint (Graphics)
//              - actionPerformed (ActionEvent)
//         > MyTreePanel
//              - MyTreePanel (MyTreeIF)
//              - setMyFont (Font)
//              - copyTree (MyTreeIF, MyTreeNode) // MyTreeNode is internal to this file
//              - walkTree (MyTreeNode, int, int) // location of node recursive method
//              - doLocations (Graphics2D)        // compute based on fonts
//              - paint (graphics)                // checks printing and valid display
//              - draw (Graphics2D)               // do update graphics
//              - drawOnGraphics (Graphics2D)     // used by printing
//              - drawSVG (Graphics2D)            // used to create SVG file
//              - print (Graphics, PageFormat, int) // used to print page
//              - printMe ()                      // print dialog
//              - sendToClipboard ()              // name says it
//              - sendToSVG ()                    // svg dialog
//         > MyTreeNode extends JButton
//              - MyTreeNode (String, MyTreeNode) // constructor, String is button label
//              - addChild (MyTreeNode)           // adds children to this node
//              - paintSVG (Graphics2D)           // draws button on SVG
//              - paintAbsolute (Graphics)        // locations used for clipboard display
//         > MyLine extends JComponent
//              - MyLine (MyTreeNode, MyTreenode) // line between centers of nodes
//              - updateLine ()                   // set bounds for this component
//              - paint (Graphics)                // draw the line
//              - toString ()                     // help debugging print statements
//         > ImageSelection implements Transferable // copied code, see comments below
//         > MySVG                                // based on Apache example, see below

   import javax.swing.JFrame;
   import javax.swing.JPanel;
   import javax.swing.JScrollPane;
   import javax.swing.JButton;
   import javax.swing.JLabel;
   import javax.swing.JComboBox;
   import javax.swing.JOptionPane;
   import javax.swing.JComponent;

   import java.awt.datatransfer.DataFlavor;
   import java.awt.datatransfer.Transferable;
   import java.awt.datatransfer.UnsupportedFlavorException;

   import java.awt.event.ActionListener;
   import java.awt.event.ActionEvent;

   import java.awt.Component;
   import java.awt.Container;
   import java.awt.Graphics;
   import java.awt.Graphics2D;
   import java.awt.GraphicsEnvironment;
   import java.awt.Toolkit;
   import java.awt.Dimension;
   import java.awt.Font;
   import java.awt.GridLayout;
   import java.awt.BorderLayout;
   import java.awt.Color;
   import java.awt.Rectangle;
   import java.awt.Insets;
   import java.awt.image.BufferedImage;

   import java.awt.print.PageFormat;
   import java.awt.print.Printable;
   import java.awt.print.PrinterJob;

   import java.util.Date;
   import java.util.ArrayList;
   import java.util.List;

   import java.io.IOException; // thrown by class ImageSelection

   import javax.swing.JFileChooser;
   import javax.swing.JOptionPane;

// *****************************************************************
// for MySVG class and SVG processing
// *****************************************************************
//svg files:
//following in: jdk/jre/lib/rt.jar
//    import org.w3c.dom.Document;
//following in: jdk/jre/lib/rt.jar
//    import org.w3c.dom.DOMImplementation;
//following in: batik-dom.jar
//    import org.apache.batik.dom.GenericDOMImplementation;
//following in: batik-svggen.jar
//    import org.apache.batik.svggen.SVGGraphics2D;
//following in: batik-svggen.jar
//    import org.apache.batik.svggen.SVGGraphics2DIOException;

//indirect reference, importing jar into runtime environment:
//batik-awt-util.jar - org.apache.batik.ext.awt.g2d.AbstractGraphics2D
//batik-util.jar     - org/apache/batik/util/SVGConstants
//batik-ext.jar      - org/w3c/dom/ElementTraversal
//batik-xml.jar      - org/apache/batik/xml/XMLUtilities

// all of the above included in:
// batik-all.jar
// *****************************************************************
// for MySVG class and SVG processing
// *****************************************************************

   public class MyDrawTreeFrame extends JFrame implements ActionListener {
      static final long serialVersionUID = -6203817511645018972L;
  
      final static int DISPLAY_W = 0;  // default width and height of the display
      final static int DISPLAY_H = 100;
      final static int MIN_BPW   = 20; // button panel width
      final static int MIN_BPH   = 20; // button panel height
   //       final static double ZOOM_JUMP = 1.1; // about zooming
  
      boolean inValid = true;
  
      MyTreePanel mtp;
      JScrollPane treeSP;
      Container cp;
  
      String  [] fontNames    = GraphicsEnvironment.getLocalGraphicsEnvironment().getAvailableFontFamilyNames();
      Integer [] fontSizeList = {10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 35, 40, 45};
      int fontSize = 12;
  
      JPanel buttonsP        = new JPanel(new GridLayout(0, 1));
      JButton printB         = new JButton("Print");
      JButton toClipB        = new JButton("Copy to Clipboard");
   //       JButton toSVGB         = new JButton ("Copy to svg file");
   //       JButton zoomInB        = new JButton("Zoom In");
   //       JButton zoomOutB       = new JButton("Zoom Out");
   //       JButton zoomResetB     = new JButton("Zoom 1.0");
      JComboBox <String> fontMenu;
      JComboBox <Integer> fontSizeMenu  = new JComboBox <Integer> (fontSizeList);
   //       JPanel buttonsPA       = new JPanel(new BorderLayout());
  
      public MyDrawTreeFrame(MyTreeIF mt) {
         this (mt, null, true);
     
} // end MyTree constructor
  
      public MyDrawTreeFrame(MyTreeIF mt, String st) {
         this (mt, st, true);
     
} // end MyTree constructor
  
      public MyDrawTreeFrame(MyTreeIF mt, String label, boolean closeOnExit) {
         setupDisplay(mt, label);
         if (closeOnExit) setDefaultCloseOperation (JFrame.EXIT_ON_CLOSE);
     
} // end MyTree constructor
  
      public void setupDisplay(MyTreeIF mt, String label) {
         int found = 0;
         for (int i = fontNames.length - 1; i > 3; i--) {
            if (fontNames[i].equals("Serif"))      found++;
            if (fontNames[i].equals("SansSerif"))  found++;
            if (fontNames[i].equals("Monospaced")) found++;
            fontNames [i] = fontNames [i - found];
         } // end removing 3 fonts from list
         fontNames [0] = "Serif"; // default font
         fontNames [1] = "SansSerif";
         fontNames [2] = "Monospaced";
         fontMenu = new JComboBox <String> (fontNames);
         fontMenu.setMaximumRowCount(30);
         fontSizeMenu.setSelectedIndex(1);
         fontSizeMenu.setMaximumRowCount(30);
     
         setTitle("Duchon's Trees - " + label);
         setLocation(300, 100);
         setLayout(new BorderLayout());
     
         mtp = new MyTreePanel(mt);
         treeSP = new JScrollPane(mtp);
         treeSP.setHorizontalScrollBarPolicy(JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);
         treeSP.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);
         add(treeSP, BorderLayout.CENTER);
     
         fontMenu.setBackground(Color.white);
         fontSizeMenu.setBackground(Color.white);
         fontSizeMenu.setAlignmentY(Component.CENTER_ALIGNMENT);
     
         JPanel pFontSize = new JPanel ();
         pFontSize .setLayout (new GridLayout (1, 0));
         pFontSize.add (new JLabel ("Font Size"));
         pFontSize.add (fontSizeMenu);
        
         printB .setToolTipText ("This won't work under jGrasp, perhaps not under any IDE?");
         toClipB.setToolTipText ("This won't work under jGrasp, perhaps not under any IDE?");
         buttonsP.add (printB);
         buttonsP.add (toClipB);
      //          buttonsP.add (toSVGB);
      //          buttonsP.add (zoomInB);
      //          buttonsP.add (zoomOutB);
      //          buttonsP.add (zoomResetB);
         buttonsP.add (fontMenu);
         buttonsP.add (pFontSize);
     
      //          buttonsPA.add (buttonsP, BorderLayout.NORTH);
         add(buttonsP, BorderLayout.SOUTH); // Compact buttons to the bottom panel
     
         printB.addActionListener(this);
         toClipB.addActionListener(this);
      //          toSVGB.addActionListener(this);
      //          zoomInB.addActionListener(this);
      //          zoomOutB.addActionListener(this);
      //          zoomResetB.addActionListener(this);
         fontMenu.addActionListener(this);
         fontSizeMenu.addActionListener(this);
     
         setSize(DISPLAY_W, DISPLAY_H);
         setVisible(true);
     
} // end setupDisplay
  
      public void paint(Graphics g) {
         super.paint(g);
         Graphics2D g2 = (Graphics2D) g;
         if (inValid) {
            mtp.doLocations(g2);
            // height + 2 to not show scroll bars by default - magic number???
            setSize(mtp.getWidth() + MIN_BPW + DISPLAY_W, Math.max (mtp.getHeight() + DISPLAY_H, MIN_BPH));
            inValid = false;
         } // end just once
     
} // end paintComponent
  
      public void actionPerformed(ActionEvent e) {
         if (e.getSource() == printB) {
            mtp.printMe();
         }
         else if (e.getSource() == toClipB) {
            mtp.sendToClipboard();
         }
//          else if (e.getSource() == toSVGB) {
//             mtp.sendToSVG();
//          }
         //          else if (e.getSource() == zoomInB) {
         //             mtp.zoomIn(ZOOM_JUMP); inValid = true;
         //          }
         //          else if (e.getSource() == zoomOutB) {
         //             mtp.zoomOut(ZOOM_JUMP); inValid = true;
         //          }
         //          else if (e.getSource() == zoomResetB) {
         //             mtp.zoomOne(); inValid = true;
         //          }
         else if (e.getSource() == fontMenu || e.getSource() == fontSizeMenu) {
            fontSize = (Integer) fontSizeMenu.getSelectedItem();
            Font x = new Font ((String)fontMenu.getSelectedItem(), Font.PLAIN, fontSize);
            mtp.setMyFont(x);
            inValid = true;
         }
      // settings
         repaint();
     
} // end method actionPerformed
  
  
} // end class MyDrawTreeFrame

   class MyTreePanel extends JPanel implements Printable {
      static final long serialVersionUID = 4765726650311548539L;
      final static int LEFT_MARGIN = 10;
      final static int TOP_MARGIN = 10;
      final static int DEPTH_DELTA = 10;
      final static int WIDTH_DELTA = 5;
  
      int printerLeftMargin = 20;
  
      Dimension dim = new Dimension(1, 1);
      boolean printFlag = false;
      boolean inValid = true;
      double printScale = 1.0;
   //       double zoom = 1.0;
      ArrayList <MyTreeNode> nodes = new ArrayList <MyTreeNode> ();
      ArrayList <MyLine    >  lines = new ArrayList <MyLine   >  ();
      MyTreeNode root;
  
   // public static Font treeFont = new Font ("SansSerif", Font.PLAIN, 12);
   // public static Font treeFont = new Font ("Serif", Font.PLAIN, 20);
   // public static Font treeFont = new Font ("Monospaced", Font.PLAIN, 14);
      Font treeFont = new Font("Serif", Font.PLAIN, 12);
  
      public MyTreePanel (MyTreeIF tp) {
         setLayout (null);
         setBackground (Color.yellow);
         root = copyTree (tp, null);
         for (MyLine d: lines) add (d);
         walkTree (root, 10, 10); // top of tree
     
} // end constructor MyTreePanel
  
   //       public void zoomIn    (double z) {
   //          zoom *= z;}
   //       public void zoomOut   (double z) {
   //          zoom /= z;}
   //       public void zoomOne   ()         {
   //          zoom  = 1.0;}
      public void setMyFont (Font fp)  {
         treeFont = fp;
         inValid = true;
     
} // end method setMyFont
     
      MyTreeNode copyTree (MyTreeIF mt, MyTreeNode parent) {
         MyTreeNode jba = new MyTreeNode (mt.toString(), parent);
         add (jba);
         for (MyTreeIF mtf : mt.getChildren()) {
            MyTreeNode jx = copyTree (mtf, jba);
            jba.addChild (jx);
            lines.add (new MyLine (jba, jx));
         }
         nodes.add (jba);
         return jba;
     
} // end method copyTree - MyTreeIF
  
      // locates nodes and lines arraylists
      MyTreeNode walkTree (MyTreeNode jba, int top, int leftEdge) {
         int minX = leftEdge;
         int next = leftEdge;
         int maxY = top;
         jba.setFont (treeFont);
         int textwidth = jba.getText().length() * 10 + 10;
         jba.setPreferredSize (new Dimension (textwidth, 29));
         Dimension d = jba.getPreferredSize ();
         jba.centerY = top + d.height / 2;
         if (jba.children == null || jba.children.size() == 0) { // is leaf
            jba.minX = leftEdge;
            jba.maxX = leftEdge + d.width;
            jba.setBounds (leftEdge, top, d.width, d.height);
            jba.centerX = leftEdge + d.width/2;
         }
         else {
            for (MyTreeNode mtif : jba.children)  {
               MyTreeNode jx = walkTree (mtif, top + DEPTH_DELTA + d.height, next);
               next = WIDTH_DELTA + jx.maxX;
               if (jx.maxY > maxY) maxY = jx.maxY;
            } // end handling child locations
            int maxX = next - WIDTH_DELTA;
            int left = maxX;
            int right = minX;
            for (MyTreeNode ch: jba.children) {
               if (ch.centerX < left) left = ch.centerX;
               if (ch.centerX > right) right = ch.centerX;
            } // end for all the children
            jba.centerX = (left + right) / 2;
            jba.setBounds (jba.centerX - d.width/2, top, d.width, d.height);
            jba.minX = minX;
            jba.maxX = maxX;
         } // end if this is a leaf
         if (top + d.height > maxY) maxY = top + d.height;
         jba.maxY = maxY;
         return jba;
      //          add (new MyLine (10, 10, 100, 200), getComponentCount()); // bottom
      //          add (new MyLine (10, 10, 200, 100), 0); // top
      //          add (new MyLine (10, 10, 200, 200)); // default is bottom
     
} // end recursive walkTree
  
      public void doLocations (Graphics2D g) {
         g.setFont (treeFont);
         MyTreeNode mtn = walkTree (root, TOP_MARGIN, LEFT_MARGIN);
         for (MyLine d: lines) d.updateLine ();
         setSize (mtn.maxX + LEFT_MARGIN, mtn.maxY + TOP_MARGIN);
         dim = getSize ();
         setPreferredSize (dim);
     
} // end method doLocations
  
      public void paint(Graphics g) { // NOT Graphics2D!!!!
      // don't call super when printing or svg
         if (!printFlag) super.paint(g);
         if (inValid)
            draw((Graphics2D) g);
     
} // end paint
  
      public void draw(Graphics2D g) {
      //          g.scale(zoom, zoom);
         g.setFont(treeFont);
         doLocations (g);
         inValid = false;
     
} // end draw
     
      public Rectangle drawOnGraphics(Graphics2D g2d) {
         g2d.setColor (Color.black);
         for (MyLine d: lines) d.paint (g2d);
         for (MyTreeNode n: nodes) n.paintAbsolute (g2d);
         return new Rectangle(dim);
     
} // end method drawOnGraphics
     
//       public void drawSVG (Graphics2D g2d) {
//          g2d.setColor (Color.black);
//          g2d.setFont (treeFont);
//          for (MyLine d: lines) d.paint (g2d);
//          for (MyTreeNode n: nodes) n.paintSVG (g2d);
//       } // end drawSVG
  
      public int print(Graphics g, PageFormat pForm, int pi) {
         if (pi > 0)
            return Printable.NO_SUCH_PAGE;
         Graphics2D g2d = (Graphics2D) g;
         g2d.translate((int) Math.round(pForm.getImageableX()), (int) Math.round(pForm.getImageableY()));
         g2d.drawString("The date is: " + new Date(), printerLeftMargin, 30);
         g2d.translate(printerLeftMargin, 40);
         g2d.scale(printScale, printScale);
         printFlag = true;
         g2d.setColor(Color.black);
         Rectangle r = drawOnGraphics(g2d);
         g2d.drawRect(0, 0, r.width, r.height);
         printFlag = false;
         return Printable.PAGE_EXISTS;
     
} // end print
  
      public void printMe() {
         PrinterJob pjPrintTreeJob = PrinterJob.getPrinterJob();
         pjPrintTreeJob.setPrintable(this);
         if (pjPrintTreeJob.printDialog()) {
            try {
               String input = JOptionPane.showInputDialog("Enter printing scale: ", "" + printScale);
               if (input == null)
                  return; // cancel button in dialog
               printScale = Double.parseDouble(input);
               pjPrintTreeJob.print();
            }
               catch (NullPointerException npe) {
                  JOptionPane.showMessageDialog(null, "MyDrawTreeFrame\nprintMe\nNullPointerException\n" + npe);
                  npe.printStackTrace();
                  return;
               }
               catch (NumberFormatException nfe) {
                  JOptionPane.showMessageDialog(null,
                     "Bad scale, aborting print job.");
                  return;
               }
               catch (Exception ex) { // NEVER crash
                  JOptionPane.showMessageDialog(null, "MyDrawTreeFrame\nprintMe\nException\n" + ex);
                  ex.printStackTrace();
               } // end try
         } // end if print selected
     
} // end printMe
  
      public void sendToClipboard() {
         if (dim.width == 0 || dim.height == 0)
            return;
         BufferedImage bi = new BufferedImage(dim.width, dim.height,
            BufferedImage.TYPE_INT_RGB);
         Graphics2D g2d = bi.createGraphics();
         g2d.setColor(Color.WHITE);
         g2d.fillRect(0, 0, dim.width, dim.height);
         printFlag = true;
         drawOnGraphics(g2d);
         printFlag = false;
         ImageSelection is = new ImageSelection(bi);
         Toolkit.getDefaultToolkit().getSystemClipboard().setContents(is, null);
     
} // end method sendToClipboard
  
//       public void sendToSVG () {
//          try {
//             printFlag = true;
//             MySVG.sendToSVG (this);
//             printFlag = false;
//          }
//             catch (Error e) {
//                JOptionPane.showMessageDialog(null, "Error:\n" + e + "\nProbably the Batik files are not part of the classpath" +
//                   "\ntry something like:\n-cp .;\"c:\\program files\\java\\batik-1.7\\lib\\batik-all-1.7.jar\"");
//             } // end try
//       } // end method sendToSVG
  
  
} // end class MyTreePanel
  
   class MyTreeNode extends JButton {
      public static final long serialVersionUID = 123978L;
      int centerX, centerY, minX, maxX, maxY;
      MyTreeNode parent;
      ArrayList <MyTreeNode> children = null;
  
      public MyTreeNode (String st, MyTreeNode pp) {
         super (st);
         parent = pp;
         setMargin (new Insets(-2, 2, -2, 2));
     
} // constructor - String
     
      public void addChild (MyTreeNode c) {
         if (children == null) children = new ArrayList <MyTreeNode> ();
         children.add (c);
     
} // end method addChild - MyTreeNode
     
      // for SVG painting, for some reason, default paint will not
//       public void paintSVG (Graphics2D g) {
//          Rectangle r = getBounds();
//          g.setColor (Color.yellow);
//          g.fillRect (r.x, r.y, r.width, r.height);
//          g.setColor (Color.black);
//          g.drawRect (r.x, r.y, r.width, r.height);
//          g.drawString (getText(), r.x + 3, r.y + r.height - 4);
//       } // end method paintSVG
     
      // for print and copy to clipboard  
      public void paintAbsolute (Graphics g) {
         Rectangle rb = getBounds ();
         paint (g.create (rb.x, rb.y, rb.width, rb.height));
     
} // end method paintAbsolute
  
  
} // end class MyTreeNode
  
   class MyLine extends JComponent {
      public static final long serialVersionUID = 123L;
      int a, b, c, d;
      MyTreeNode m1, m2;
  
      public MyLine (MyTreeNode n1, MyTreeNode n2) {
         m1 = n1; m2 = n2;
     
} // end constructor - MyTreeNode, MyTreeNode
     
      public void updateLine () {
         a = m1.centerX; b = m1.centerY; c = m2.centerX; d = m2.centerY;
         int w = (a > c) ? a+1 : c+1; // add 1 to make sure vertical and horizontal lines show
         int h = (b > d) ? b+1 : d+1;
         setBounds (0, 0, w, h); // otherwise nothing will show on paint!
     
} // end updateLine
  
      public void paint (Graphics g) {
         g.drawLine (a, b, c, d);
     
} // end paintComponent for this instance
  
      public String toString () {
         return String.format ("Line from (%d,%d) to (%d,%d)", a, b, c, d);
     
} // end method toString
  
  
} // end class MyLine

// this code from :
// http://www.devx.com/Java/Article/22326/
// by: Kulvir Singh Bhogal
// Local class is used to hold an image while on the clipboard.
   class ImageSelection implements Transferable {
   // the Image object which will be housed by the ImageSelection
      private BufferedImage image;
  
      public ImageSelection(BufferedImage image) {
         this.image = image;
     
} // end constructor - BufferedImage
  
   // Returns the supported flavors of our implementation
      public DataFlavor[] getTransferDataFlavors() {
         return new DataFlavor[] { DataFlavor.imageFlavor };
     
} // end method getTransferDataFlavors
  
   // Returns true if flavor is supported
      public boolean isDataFlavorSupported(DataFlavor flavor) {
         return DataFlavor.imageFlavor.equals(flavor);
     
} // end method isDataFlavorSupported - DataFlavor
  
   // Returns Image object housed by Transferable object
      public Object getTransferData(DataFlavor flavor)
          throws UnsupportedFlavorException, IOException {
         if (!DataFlavor.imageFlavor.equals(flavor)) {
            throw new UnsupportedFlavorException(flavor);
         }
      // else return the payload
         return image;
      } // end method getTransferData - DataFlavor
     
   } // end class ImageSelection

//    class MySVG {
   // NOTE: uses paint in calling method,
   // >> If paint starts with a call to super, put the call inside a try/catch block
   //     catching NullPointerException - SVG will not have a super instance
   // based on example from apache batik
   // http://xmlgraphics.apache.org/batik/using/svg-generator.html
//       public static void sendToSVG (MyTreePanel cmp) {
//          try {
//             String fileName = "tree.svg"; // file to save svg output
//          //             JFileChooser chooser = new JFileChooser("c:\\inet\\home");
//             JFileChooser chooser = new JFileChooser("Desktop");
//             int returnVal = chooser.showOpenDialog(null);
//             if ( returnVal == JFileChooser.APPROVE_OPTION ) {
//                fileName = chooser.getSelectedFile().getAbsolutePath();
//             }
//             else
//                return;
        
         // Get a DOMImplementation.
         // from: org.apache.batik.dom.GenericDOMImplementation
         //         import org.w3c.dom.Document;
         //       import org.w3c.dom.DOMImplementation;
         //       import org.apache.batik.dom.GenericDOMImplementation;
//             DOMImplementation domImpl = GenericDOMImplementation.getDOMImplementation();
        
         // Create an instance of org.w3c.dom.Document.
         // no special imports required here
//             String svgNS = "http://www.w3.org/2000/svg";
//             Document document = domImpl.createDocument(svgNS, "svg", null);
        
         // Create an instance of the SVG Generator.
         // from: org.apache.batik.svggen.SVGGraphics2D
         //       import org.apache.batik.svggen.SVGGraphics2D;
//             SVGGraphics2D svgGenerator = new SVGGraphics2D(document);
        
         // Render into the SVG Graphics2D implementation.
//             cmp.drawSVG(svgGenerator);
        
//             svgGenerator.stream(fileName, true); // use CSS style
//             JOptionPane.showMessageDialog(null, "File saved as:\n" + fileName);
//             svgGenerator.dispose(); // flush the stream, I hope!
//          }
//             catch (SVGGraphics2DIOException e) {
//                JOptionPane.showMessageDialog(null, "MySVG\nsndToSVG\nSVGGraphics2DIOException\n" + e);
//             }
//             catch (Exception e) {
//                JOptionPane.showMessageDialog(null, "MySVG\nsndToSVG\nException\n" + e);
//                e.printStackTrace();
//             } // end try
//      
//       } // end method sndToSVG
//    } // end class MySVG


Code: MyTreeIF.java

// File: MyTreeIF.java
// Author: Nicholas Duchon
// Date: Nov 1, 2012
// Purpose: interface to support the MyDrawTreeFrame class
//   to simplify the graphic display of trees.
// Instructions:
//   To use these classes, create a data container class, a kind of node, say MyNode,
//   which will implement the getChildren () method - returning
//   a list of children. The return value may be null.
//   MyNode should implement MyTreeIF and return a list of children which
//   are also instances of MyNode.
// See - the TestTree.java file for an example using these classes.
// Also: the MyDrawTreeFrame uses the toString method of the class that
//   implements MyTreeIF, so you will want to make sure that toString makes sense.

import java.util.List;

interface MyTreeIF {
  public List <MyTreeIF> getChildren();
} // end MyTreeIF

ND.