// Tree Traversal Demonstration, featuring: // Quick and dirty mplementation of (full) binary trees // (CBTreeNode and CBTree) // Simple wrapping of util.LinkedList functions to sound like Queues // Menus, Button, and HTML parameter for user interaction // CONTENTS // // BinInter -- the applet code and interaction manager // CBTree -- Binary Tree class, including traversals // GeoTree -- Extends CBTree with X-Y screen location info // CBTreeNode -- Node class, including what to do when visited // TreeConstants -- Use of interface to get global constants // CBQueue -- Super-simple and unneeded wrapper for Linked // List class to show use of utility classes. // ========== BinInter.java ================== // Mostly the interaction manager; menus, button, a little logic for // managing (more or less) what happens when... import java.awt.*; // it's IMPORTant not to import also java.util.* unless necessary, // since then you have ambiguity between awt.LIST and util.LIST classes import java.awt.Graphics; import java.awt.Color; import java.awt.event.*; import java.applet.Applet; public class BinInter extends Applet implements TreeConstants, ItemListener { private GeoTree aTree; // the full binary tree to be drawn. // a GeoTree has nodes with X,Y location for drawing. private boolean makeNewTree = true; // do we need to create a new tree? private int treeDepth = 3; // default private int oldTreeDepth = 3; // did user change depth? private int traverseType = LEVEL; // Traversal Type private Color treeColor = Color.red; // default private int myHeight, myWidth; // size of this applet String parameter; // read from the .html file int wait; // its value...node painting delay // following set up the menus and buttons private List colorList, traversalList, depthList; // awt lists for menus private Button goButton; // to start painting // what color to paint nodes when they get "visited" private String colorNames[] = { "Red", "Green", "Yellow", "Cyan", "Orange", "Magenta", "Blue"}; private Color colors[] = { Color.red, Color.green, Color.yellow, Color.cyan, Color.orange, Color.magenta, Color.blue }; // four traversal types private String traversalNames[] = {"PreOrder", "PostOrder", "InOrder", "LevelOrder"}; private int traversalCodes[] = {PRE, POST, IN, LEVEL}; // how big tree can be private String depthNames[] = {"1", "2", "3", "4", "5"}; private int depths[] = {1,2,3,4,5}; // here we go... public void init() { fixLists(); // set up user interaction parameter = getParameter("delay"); // read html for paint speed wait = (parameter == null? 200: Integer.parseInt (parameter)); myHeight= this.getSize().height; // how big is the applet? myWidth = this.getSize().width; // used to scale tree size } // Do all the painting and a fair amount of the logic in here... public void paint(Graphics g) { setBackground(Color.white); // to show off schmantzy colors showStatus ("Defaults: Depth 3, Red, LevelOrder"); if (makeNewTree) // if no tree or it's changed size { aTree = new GeoTree(treeDepth,0,myWidth,myHeight); makeNewTree = false; } if (aTree != null) // don't follow null references... { // treeColor and traverseType set via user interaction aTree.setDelayTicks(0); // draw black tree fast aTree.setGraphics(g); // tell it the graphics structure aTree.setnodeColor(Color.black); // it'll have black nodes aTree.preOrderPaint(); // paint it up aTree.setDelayTicks(wait); // set speed to user's wish aTree.setnodeColor(treeColor); // ditto the node color switch (traverseType) { // do user's bidding case PRE: aTree.preOrderPaint(); break; case POST: aTree.postOrderPaint(); break; case IN: aTree.inOrderPaint(); break; case LEVEL: aTree.levelOrderPaint(); break; default: break; } } goButton.setBackground(Color.red.darker()); } // user interaction ... all this stolen from Deitel^2 private void fixLists() { // show 3 items max, I forget what false is...only 1 choice? colorList = new List (3, false); traversalList = new List (3, false); depthList = new List (3, false); colorList.addItemListener(new colorHandler(this)); traversalList.addItemListener(new traversalHandler(this)); depthList.addItemListener(new depthHandler(this)); goButton = new Button("GO!"); goButton.setBackground(Color.red.darker()); goButton.addActionListener ( new goButtonHandler (this)); // all those above Handlers are simple instance wrappers // now set up menues and screen for (int i = 0; i