HW2 Solutions Page
Return to
homework page.
4.9 (a)
Step 1: insert 3 Step 2: insert 1 Step 3: insert 4
======= ======= =======
(3) (3) (3)
/ / \
(1) (1) (4)
Step 5: insert 6 Step 6: insert 9 Step 7: insert 2
======= ======= =======
(3) (3) (3)
/ \ / \ / \
(1) (4) (1) (4) (1) (4)
\ \ \ \
(6) (6) (2) (6)
\ \
(9) (9)
Step 8: insert 5 Step 9: insert 7
======= =======
(3) (3)
/ \ / \
(1) (4) (1) (4)
\ \ \ \
(2) (6) (2) (6)
/ \ / \
(5) (9) (5) (9)
/
(7)
4.9 (b) Delete 3 from last tree above.
Step 1
======
3 has two children in above tree so we find the minimal element
in the right subtree of 3. This is 4. So we store 4 in 3's node to get
(4)
/ \
(1) (4)
\ \
(2) (6)
/ \
(5) (9)
/
(7)
Now we do a remove 4 on the right subtree of the root. Since 4 has only
one subtree, we set the right subtree of the root to be this subtree.
Hence we get:
(4)
/ \___
(1) (6)
\ / \
(2)(5) (9)
/
(7)
//cs146sec6hw2file1.java - an application to parse and draw ShML files
import java.awt.*; // for drawing
import java.awt.event.*; // for window closing
import java.awt.geom.*; // for Rectangle
import javax.swing.*; // for drawing
import java.util.*; // for Stack
import java.io.*; // to read files
/**
Objects of this class read in ShML files, parse them and draw
them in frames. This class can be run as an application from
the command line with a line like
java cs146sec6hw2file filename
where filename is the name of an ShML file.
@author Chris Pollett
@version 1.0
*/
public class cs146sec6hw2file1 extends JFrame
{
protected ShMLShape docFigure; /*
Outermost shape to be drawn
This is a black ShMLSquare
on which all the other objects
from the shmlfile are put
*/
public static final int DEFAULT_X_SZ = 400; // default frame sizes
public static final int DEFAULT_Y_SZ = 400;
/**
The constructor reads file into docFigure ShMLShape. Sets
title and color of frame.
@param name - name of file to be read.
*/
public cs146sec6hw2file1( String name)
{
super("ShML Browser");
docFigure=parseShMLDoc(name);
setBackground(Color.black);
}
/**
Sets how big the frame to view the ShML file should be.
Also sets how big outermost ShMLShape docFigure should be.
*/
public void setSize(int x, int y)
{
docFigure.setRectangle(new Rectangle(5,22,x,y));
super.setSize(x,y);
}
/**
Called whenever our frame needs to be painted.
This method just draws the top level shape on itself.
*/
public void paint(Graphics g)
{
docFigure.draw(g);
}
/**
Reads in an shml file and parse it into a ShMLSquare
@param shmlFile - file containing shml tags
@return the ShMLShape described by the shml tags
added to a ShMLSquare the size of the frame.
@see parseShMLLine
*/
public ShMLShape parseShMLDoc(String shmlFile)
{
Stack shapeStack = new Stack();
ShMLShape figure = new ShMLSquare(); // root ShMLShape we will return
String line;
shapeStack.push(figure);
try
{
BufferedReader buf= new BufferedReader(new FileReader(shmlFile));
while((line = buf.readLine()) != null)
{
parseShMLLine(line,shapeStack);
}
buf.close();
}
catch(FileNotFoundException fe)
{
System.err.println("File not found");
System.exit(1);
}
catch(IOException ie)
{
System.err.println("An I/O Exception occurred:"+ie.toString());
System.exit(1);
}
catch(Exception ee) //will get here if parseShMLLine gets stuck
{
System.err.println("The provided file was not a valid ShML file.");
System.exit(1);
}
if(shapeStack.size() != 1)
{
System.err.println("The provided file was not a valid ShML file.");
System.exit(1);
}
figure.setColor(Color.black); // root shape is black.
return figure;
}
/**
Parses a line of shml tags, create shape objects
in correct tree structure and add them
to stack.
@param line - a String of shml tags
@param stack - a Stack of ShMLShape object
@throws Exception - if string not parseable
*/
public void parseShMLLine(String line, Stack stack)
throws Exception
{
StringTokenizer tokens = new StringTokenizer(line);
String cur;
ShMLShape fig;
ShMLShape tmp=new ShMLShape();
while(tokens.hasMoreTokens())
{
cur = tokens.nextToken("<");
fig = (ShMLShape)stack.pop();
if(cur.equals("square>") || cur.equals("circle>") ||
cur.equals("triangle>"))
{
if(cur.equals("square>")) tmp = new ShMLSquare();
if(cur.equals("circle>")) tmp = new ShMLCircle();
if(cur.equals("triangle>")) tmp = new ShMLTriangle();
fig.add(tmp);
stack.push(fig);
stack.push(tmp);
}
else if( cur.trim().equals("") ) /* don't change top of
stack if see white space
*/
{
stack.push(fig);
}
else if(!( (cur.equals("/square>") && fig instanceof ShMLSquare) ||
(cur.equals("/circle>") && fig instanceof ShMLCircle) ||
(cur.equals("/triangle>") &&fig instanceof ShMLTriangle)
)
) //not correct tag or symbol so bail
{
throw new Exception();
}
}
}
// Main entry point
public static void main(String[] args)
{
if( args.length == 0 )
{
System.err.println("You need to give as a comand line " +
"argument an ShML file.");
System.exit(1);
}
cs146sec6hw2file1 app= new cs146sec6hw2file1(args[0]);
if(args.length == 3)
{
app.setSize(Integer.parseInt(args[1]),
Integer.parseInt(args[2]));
}
else
{
app.setSize(DEFAULT_X_SZ, DEFAULT_Y_SZ);
}
app.show();
app.addWindowListener( new WindowAdapter() //anonymouse inner class
{
public void windowClosing( WindowEvent e)
{
System.exit(0);
}
}
);
}
/**
Base class from which all shapes derived.
Provides basic functionality to draw a shape and its children to
a graphics context and to arrange subshapes on a shape.
Notice used inner classes. This was to keep the javadoc functionality.
*/
public static class ShMLShape
{
protected Color color; // color of shape
protected Polygon shape; // polygon used to draw shape
protected Rectangle interior; /* an open Rectangle
on which subShapes can be drawn */
protected boolean curOrganized; /* flag to ck if we've set
the rectangle's for sub shapes*/
protected ArrayList subShapes; // child shapes attached to this one
/**
Initial array of child shapes on shape and
polygon used to draw shape. Shapes not organized yet.
*/
public ShMLShape()
{
subShapes =new ArrayList();
shape = new Polygon();
curOrganized = false;
}
/**
This method set the size of the exterior rectangle
for shape. By default we say this is the same as the interior
rectangle.; however, we will override this.
@param ex - Rectangle that just bounds exterior of shape
*/
public void setRectangle(Rectangle ex)
{
interior=ex;
}
/**
Sets the color of current shape
@param c - color shape changed to
*/
public void setColor(Color c)
{
color=c;
}
/**
Adds sub shape to the list of shapes on this ShMLShape
@param s - subshape to be added
*/
public void add(ShMLShape s)
{
subShapes.add(s);
}
/*
Divides the interior rectangle into subrectangle
used to set the exterior rectangles of subshapes.
*/
private void organize()
{
ShMLShape curSubShape;
Rectangle r;
Iterator iter = subShapes.iterator();
int size = subShapes.size();
int x = interior.x;
int y = interior.y;
int height = interior.height;
int width = interior.width;
if ( size> 0) width = width/size;
while(iter.hasNext())
{
curSubShape = (ShMLShape)(iter.next());
r=new Rectangle(x+1,y+1,width-1, height-1);
curSubShape.setRectangle(r);
curSubShape.organize();
x+=width;
}
curOrganized = true;
}
/*
Draws just the current ShMLShape
*/
protected void drawShape(Graphics g)
{
g.setColor(color);
g.fillPolygon(shape);
}
/**
Draws shape
*/
public void draw(Graphics g)
{
ShMLShape tmp;
if(!curOrganized) organize();
Iterator shapeIter = subShapes.iterator();
drawShape(g);
while(shapeIter.hasNext())
{
tmp=(ShMLShape)(shapeIter.next());
tmp.draw(g);
}
}
}
/**
Derived type of ShMLShape used to draw a triangle.
*/
public static class ShMLTriangle extends ShMLShape
{
/**
Initialize triangle color to red. Implicit call
to ShMLShape default constructor.
*/
public ShMLTriangle()
{
color= Color.red;
}
/**
Uses the exterior rectangle to set the coordinates
for the triangle's polygon. Then calculates interior
rectangle.
@param ex - exterior rectangle
*/
public void setRectangle(Rectangle ex)
{
int x = ex.x, y =ex.y;
int width = ex.width, height = ex.height;
int side = (width > height) ? height : width;
int[] xPoints = {x, x+side/2, x+side};
int[] yPoints = {y+side, y, y+side};
shape=new Polygon( xPoints, yPoints, 3);
interior =new Rectangle(x+side/4,y+side/2, side/2, side/2);
}
}
/**
Derived type of ShMLShape used to draw a square.
*/
public static class ShMLSquare extends ShMLShape
{
/**
Initialize square color to blue. Implicit call
to ShMLShape default constructor.
*/
public ShMLSquare()
{
color=Color.blue;
}
/**
Uses the exterior rectangle to set the coordinates
for the square's polygon. Then calculates interior
rectangle.
@param ex - exterior rectangle
*/
public void setRectangle(Rectangle ex)
{
int x = ex.x;
int y = ex.y;
int width = ex.width;
int height = ex.height;
int side = (width > height) ? height : width;
int[] xPoints = {x, x, x+side, x+side};
int[] yPoints = {y, y+side, y+side, y};
shape = new Polygon(xPoints, yPoints, xPoints.length);
interior = new Rectangle(x+1, y+1, side-1, side-1);
}
}
/**
Derived type of ShMLShape used to draw a circle.
*/
public static class ShMLCircle extends ShMLShape
{
private Rectangle exterior; /* rectangle used to bound outside of
circle.
*/
private double root2Over2 = Math.sqrt(2)/2; /* used to calculate
interior rectangle
*/
private double offsetScaling = (1-root2Over2)/2; /* used to calculate
rectangle
*/
/**
Initialize circle color to green. Implicit call
to ShMLShape default constructor.
*/
public ShMLCircle()
{
color = Color.green;
}
/**
Sets both the interior and exterior rectangles for circles
@param ex - exterior rectangle to set to
*/
public void setRectangle(Rectangle ex)
{
int x = ex.x;
int y = ex.y;
int width = ex.width;
int height = ex.height;
int side = (width > height) ? height : width;
int interSide = (int)(side*root2Over2);
int offset = (int)(offsetScaling*side);
interior = new Rectangle(x + offset, y+offset,
interSide, interSide );
exterior = new Rectangle(x , y, side, side );
}
/*
Draw the current circle. Notice don't use a Polygon.
*/
protected void drawShape(Graphics g)
{
g.setColor(color);
g.fillOval(exterior.x, exterior.y, exterior.width, exterior.height);
}
}
} //end cs146sec6hw2file1.java