import java.awt.*;
import java.applet.Applet;

public class TreeTraversal extends Applet {

	final int r = 35;			// node radius
	Choice c;					// traversal method list
	Button start, reset;		// start and reset buttons
	String method = "PREORDER";	// traversal method
	
	// Conversion table from int to char
	char[] labels = {'0','1','2','3','4','5','6','7','8','9'};

	// Order which nodes are visited
	int[] pre = {0,1,3,4,7,8,2,5,9,6};		// preorder
	int[] inord = {3,1,7,4,8,0,9,5,2,6};	// inorder
	int[] post = {3,7,8,4,1,9,5,6,2,0};		// postorder

	// Whether nodes have been visited or not 
	boolean[] visited = new boolean[10];


	// XY Coordinates for each node of tree 
	Point[] coord = {new Point(250,50), new Point(125,100),new Point(375,100),
				      new Point(62,150), new Point(188,150),new Point(312,150),
				      new Point(438,150),new Point(156,200),new Point(219,200),
				      new Point(281,200)};

	// List of adjacent nodes (x is parent of y)
	Point[] adj = {new Point(0,1),new Point(0,2),new Point(1,3),new Point(1,4),
			        new Point(2,5),new Point(2,6),new Point(4,7),new Point(4,8),
				    new Point(5,9)};

	void initVisited() {

		// Set all the nodes to unvisited
		for (int i = 0; i < 10; i++)
			visited[i] = false;
	}


	public void init() {

		// Initialize the visited array
		initVisited();
		
		// Make label
		Label l = new Label("Tree Traversal in:");
		add(l);

		// Make choice list
		c = new Choice();
		c.addItem("PREORDER");
		c.addItem("POSTORDER");
		c.addItem("INORDER");
		add(c);

		// Make button
		start = new Button("Start");
		reset = new Button("Reset");
		add(start);
		add(reset);
		reset.disable();
	} // init


	public void paint (Graphics g) {
	
		g.setColor(Color.white);
		
		// Display tree
		// Draw the edges
		for (int i = 0; i < 9; i++) {

			// Get node coordinates
			Point parent = coord[adj[i].x];
			Point child = coord[adj[i].y];

			// Draw the connecting lines
			g.drawLine(parent.x+r/2, parent.y+r/2, child.x+r/2, child.y+r/2);
		}

		// Draw the nodes
		for (int i = 0; i < 10; i++) {

			// Set the color blue = unvisited, red = visited
			if (visited[i])
				g.setColor(Color.red);
			else
				g.setColor(Color.blue);

			// Draw node i in the appropriate colour with label
			g.fillOval(coord[i].x, coord[i].y, r, r);
			g.setColor(Color.black);
			g.drawChars(labels, i, 1, coord[i].x, coord[i].y);
		}
	} // paint


	public boolean action(Event e, Object o) {

		// Changing traversal method
		if (e.target instanceof Choice)	{
			method = (String) o;
		}

		// Button was pressed
		if (e.target instanceof Button) {
			
			if (e.target == start) { // Start was pressed

				// Disable the buttons
				c.disable();
				start.disable();
			
				// Traverse the tree with the desired method
				if ("PREORDER".equals(method))
					Traverse(pre);
				else if ("POSTORDER".equals(method))
					Traverse(post);
				else
					Traverse(inord);

				reset.enable();
			}
			else { // Reset was pressed

				// Enable/disable the buttons
				c.enable();
				start.enable();
				reset.disable();

				// Reset the visited array
				initVisited();

				repaint();
			}
		}
		return true;
	} // action


	void Traverse(int[] order) {

		Graphics g = getGraphics();
		g.setColor(Color.black);
		g.drawString("Traversal order: ", 100, 275);

		for (int i = 0; i < 10; i++) {

			// Get the nodes number
			int j = order[i];

			// Print out which node is being visited at bottom
			g.setColor(Color.black);
			g.drawChars(labels, j, 1, 200+20*i, 275); 

			// Fill in the ith node and record it as visited
			g.setColor(Color.red);
			g.fillOval(coord[j].x, coord[j].y, r, r);
			visited[j] = true;

			// Delay
			for(long k = 0; k < 500000; k++);
		}

		g.setColor(Color.black);
		g.drawString("... Done!", 400, 275);

	} // traverse
} // class