/** * Class Node holds 1 String value per node. * Nodes are meant to be used in Binary Trees. * @author David Thibodeau * @version 23-July-2002 */ public class Node { public String sData; // data item (key) public Node leftChild; // this node's left child public Node rightChild; // this node's right child /** * Constructor for objects of class Node */ public Node() { } // end Node() Constructor /** * displayNode method - Displays the values of sData * for this node. * @param void * @return void */ public void displayNode() // display ourself { System.out.print('{'); System.out.print(sData.toLowerCase() ); System.out.println("} "); } // end displayNode() } // end Class Node Class Tree: /** * Class Tree uses node objects to create a binary * search tree. * @author CS152 text, modified by David Thibodeau * @version 12-May-2002 */ public class Tree { private Node root; // first node of tree /** * Constructor for objects of class Tree */ public Tree() // constructor { root = null; } // no nodes in tree yet /** * find method - finds the supplied String if there * is a Node object with a match & returns a pointer * or returns null if there is no match. * @param String A String value to search for. * @return Node Returns a pointer to the Node with a match * or null if not found. */ public Node find(String key) // find node with given key { // (assumes non-empty tree) key = key.toLowerCase(); // convert srch string to lowercase Node current = root; // start at root while(current.sData.compareTo(key) != 0 ) { // while no match, if( key.compareTo(current.sData.toLowerCase() ) < 0 ) current = current.leftChild; // go left? 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(String sd) { Node newNode = new Node(); // make new node // Node findNode = new Node(); newNode.sData = sd; // insert data if(root == null) // no node in root { root = newNode; } else // root occupied { // newNode.sData = sd; // no matches were found so a // new Node will be created Node current = root; // start at root Node parent; while(true) // (exits internally) { parent = current; sd = sd.toLowerCase(); // Make lowercase for evaluation if(sd.compareTo( current.sData.toLowerCase() ) < 0 ) { // 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 void traverse(int traverseType) { switch(traverseType) { case 1: System.out.print("\nPreorder traversal: "); preOrder(root); break; case 2: System.out.print("\nInorder traversal: "); inOrder(root); break; case 3: System.out.print("\nPostorder traversal: "); postOrder(root); break; } System.out.println(); } // ------------------------------------------------------------- private void preOrder(Node localRoot) { if(localRoot != null) { localRoot.displayNode(); preOrder(localRoot.leftChild); preOrder(localRoot.rightChild); } } // ------------------------------------------------------------- private void inOrder(Node localRoot) { if(localRoot != null) { inOrder(localRoot.leftChild); localRoot.displayNode(); inOrder(localRoot.rightChild); } } // ------------------------------------------------------------- private void postOrder(Node localRoot) { if(localRoot != null) { postOrder(localRoot.leftChild); postOrder(localRoot.rightChild); localRoot.displayNode(); } } } // end class Tree Class Document: /** * Class Document is used to read data from disk files, * and insert the data into binary search trees. * * @author David Thibodeau * @version 14-Apr-2002 modified 23-July-2002 */ import java.io.*; import java.util.*; public class Document { private Tree docTree; /** * Constructor for objects of class Document */ public Document() { docTree = new Tree(); // new empty obj } // end of Document Constructor /** * readInFromFile method - This reads the specified file * * @param infilename the name of the file to be opened * @return void */ public void readInFromFile(String infilename) { String line; // holds a line of text brought in from the file // try - catch block of code from teacher's online CS151 // and modified by me to call addToLinkList method. try // this routine pulls in lines of text from the file { BufferedReader in = new BufferedReader( new FileReader( infilename ) ); line = in.readLine(); // read first line of text file while ( line != null ) // continue until end of file { addToTree( line ); // send line of text to // be added to linked list line = in.readLine(); // read next line in text file } in.close(); // closes text file } // end of try block catch ( IOException iox ) // couldn't find the file { System.out.println("Problem reading " + infilename ); } // end of catch block } // end of readInFromFile(String infilename) /** * outputTree method - outputs the tree values, which are * traversed Pre- In- or Post- order based on the int value * passed to the method * @param travtype 1 = Preorder, 2 = Inorder & 3 = Postorder * @return void */ public void outputTree(int travtype) { docTree.traverse(travtype); } // end of writeColumnToFile(String outfilename, int width) /** * addToTree method - Takes a String and tokenizes it, * then adds each token to the docTree object. * @param toAdd String to be tokenized * @return void */ public void addToTree(String toAdd) { docTree.insert( toAdd ); // add String to Tree } // end of addToTree(String toAdd) method } Class DocumentGUI: /** * Class DocumentGUI provides a GUI front end for the class Document. * DocumentGUI creates the visual layout and ties the proper actions * to each interface element. * * @author David Thibodeau * @version 24-July-2002 */ import java.awt.* ; import java.awt.event.*; import javax.swing.*; public class DocumentGUI extends JFrame implements ActionListener { // data input panel JLabel inputLabel; JTextField inputText; JButton inputButton; JPanel inputPanel; JRadioButton inputFileRadioButton; JRadioButton inputTextRadioButton; ButtonGroup inputType; // Holds the two RadioButtons // Output options panel JLabel outputLabel; JButton outputButton; JPanel outputPanel; JRadioButton outputPreOrder; JRadioButton outputInOrder; JRadioButton outputPostOrder; ButtonGroup outputType; // Holds the 3 output order type RadioButtons Document bandList; /** * Constructor for objects of class DocumentGUI */ public DocumentGUI() { bandList = new Document(); // initiate Document object setTitle( "Binary Search Tree Example" ); setDefaultCloseOperation( EXIT_ON_CLOSE ); // input group inputLabel = new JLabel( "Input Band Name Here:" ); inputText = new JTextField(30); inputButton = new JButton( "Add Name" ); inputButton.addActionListener(this); inputButton.setActionCommand( "AddName" ); // Set to add a single name to the tree inputTextRadioButton = new JRadioButton( "Enter Band Name", true ); inputTextRadioButton.addActionListener(this); inputTextRadioButton.setActionCommand( "UseName" ); inputFileRadioButton = new JRadioButton( "Enter Filename", false ); inputFileRadioButton.addActionListener(this); inputFileRadioButton.setActionCommand( "UseFile" ); inputType = new ButtonGroup(); inputType.add ( inputTextRadioButton ); inputType.add ( inputFileRadioButton ); inputPanel = new JPanel(); inputPanel.add ( inputLabel ); inputPanel.add ( inputText ); inputPanel.add ( inputButton ); inputPanel.add ( inputTextRadioButton ); inputPanel.add ( inputFileRadioButton ); // output group outputLabel = new JLabel ( "Select Output Order:" ); outputButton = new JButton ( "Create Output" ); outputButton.addActionListener(this); outputButton.setActionCommand( "Output" ); outputPreOrder = new JRadioButton ( "PreOrder", true ); outputInOrder = new JRadioButton ( "InOrder", false ); outputPostOrder = new JRadioButton ( "PostOrder", false ); outputType = new ButtonGroup(); outputType.add ( outputPreOrder ); outputType.add ( outputInOrder ); outputType.add ( outputPostOrder ); outputPanel = new JPanel(); outputPanel.add ( outputLabel ); outputPanel.add ( outputPreOrder ); outputPanel.add ( outputInOrder ); outputPanel.add ( outputPostOrder ); outputPanel.add ( outputButton ); // content pane getContentPane().setLayout( new BoxLayout( getContentPane(), BoxLayout.Y_AXIS ) ); getContentPane().add( inputPanel ); getContentPane().add( outputPanel ); } /** * actionPerformed method. This method handles the GUI click events * for the application. In the input section, the radiobutton selection * determines whether the textfield should hold a band name or a file * name. When the Enter button is pressed, either the band name will be * added to the tree, or the specified file will be opened (if it exists) * and all lines of text will be added to the tree. When the file is read * each line will be considered a band name. * For the output section, select the output order desired, then click * the output button. The output will then be sent to the console. * @param ActionEvent supplied by Java's Swing event handler * @return void */ public void actionPerformed( ActionEvent evt ) { if ( evt.getActionCommand().equals( "UseName" ) ) { inputButton.setText ( "Add Name" ); inputButton.setActionCommand ( "AddName" ); inputLabel.setText( "Input Band Name Here:" ); } else if ( evt.getActionCommand().equals( "UseFile" ) ) { inputButton.setText ( "Open File" ); inputButton.setActionCommand ( "OpenFile" ); inputLabel.setText( "Input Filename Here:" ); } else if ( evt.getActionCommand().equals( "OpenFile" ) ) { bandList.readInFromFile ( inputText.getText() ); } else if ( evt.getActionCommand().equals( "AddName" ) ) { bandList.addToTree ( inputText.getText() ); } else if ( evt.getActionCommand().equals( "Output" ) ) { if ( outputPreOrder.isSelected() ) { bandList.outputTree(1); } else if ( outputInOrder.isSelected() ) { bandList.outputTree(2); } else if ( outputPostOrder.isSelected() ) { bandList.outputTree(3); } } } /** * main method. This creates a new instance of DocumentGUI, then * instantiates a new WindowQuitter() object and lastly sets the * size and visibility of the GUI window. */ public static void main ( String[] args ) { // New GUI instance DocumentGUI docApp = new DocumentGUI(); // New WindowQuitter instance WindowQuitter wquit = new WindowQuitter(); docApp.addWindowListener( wquit ); // Set window size & make visible docApp.setSize( 400, 200 ); docApp.setVisible( true ); } // end main } // end Class DocumentGUI class WindowQuitter extends WindowAdapter { public void windowClosing( WindowEvent e ) { System.exit( 0 ); } }