bintree.java

java算法大全

	for (int i = 0; i < nodeList.size(); i++) {
	    Node node = (Node)nodeList.elementAt(i);
	    drawNode(g, node);
	}

	if (movingNode.getWeight() > -1)
	    drawNode(g, movingNode);
    }

    public void drawBox(Graphics g, int x, int y, String str,
                                Color fg, Color bg, Font font) {
	String blank = new String();
	for (int i = 0; i < 4-str.length(); i++)
	    blank = blank.concat(" ");
        g.setColor(bg);
        g.fillRect(x, y, horizSpace, vertSpace);
        g.setColor(Color.black);
        g.drawRect(x, y, horizSpace, vertSpace);
        g.setColor(fg);
        g.setFont(font);
        g.drawString(blank + str, x + 2, y + vertSpace - 4);
    }

    /**
     * Draw an arrowed line segment using the array of points.
     * @param g Graphical context
     * @param points The vortices of the line segment. 
     * An arrow head will be drawn using the last point in the array at the tip.
     */
    public void drawArrow(Graphics g, Point[] points) {
	// remember: no drawPolyline in jdk1.0.*
	int[] axPoints = new int[3], ayPoints = new int[3];
	g.setColor( Color.magenta );
	if (points.length < 3) {
	  Point endArrow = points[1], startArrow = points[0];
	  if (endArrow.y == startArrow.y) {
	    g.drawLine(startArrow.x, startArrow.y, endArrow.x, endArrow.y);
	    axPoints[0] = endArrow.x; ayPoints[0] = endArrow.y;
	    int unit = (endArrow.x - startArrow.x)/
			Math.abs(endArrow.x - startArrow.x);
	    axPoints[1] = endArrow.x - unit*2;
	    ayPoints[1] = endArrow.y - 2;
	    axPoints[2] = endArrow.x - unit*2;
	    ayPoints[2] = endArrow.y + 2;
	    g.fillPolygon(axPoints, ayPoints, 3);
	  } else if (endArrow.x == startArrow.x) {
	    g.drawLine(startArrow.x, startArrow.y, endArrow.x, endArrow.y);
	    axPoints[0] = endArrow.x; ayPoints[0] = endArrow.y;
	    int unit = (endArrow.y - startArrow.y)/
			Math.abs(endArrow.y - startArrow.y);
	    axPoints[1] = endArrow.x - 1;
	    ayPoints[1] = endArrow.y - unit*2;
	    axPoints[2] = endArrow.x + 2;
	    ayPoints[2] = endArrow.y - unit*2;
	    g.fillPolygon(axPoints, ayPoints, 3);
	  }
	} else if (points.length == 3) {
	    // draw a line for the first and second points then use
	    // drawArrow to draw the remaining segment
	    g.drawLine(points[0].x, points[0].y, points[1].x, points[1].y);
	    Point[] line = new Point[2];
	    line[0] = points[1];
	    line[1] = points[2];
	    drawArrow(g, line);
	}
    }

    /**
     * @param node The root node of the tree
     * @return The width of the tree in the number of pixels.
     */
    public int treeWidth(Node node) {
        return (rightMostPosn(node) - leftMostPosn(node));
    }
 
    /**
     * @param node The root node of the tree
     * @return The left most position of the tree
     */
    public int leftMostPosn(Node node) {
        if (node.isLeaf())
            return node.x;
        else
            return leftMostPosn(node.getLeftNode());
    }
 
    /**
     * @param node The root node of the tree
     * @return The right most position of the tree
     */
    public int rightMostPosn(Node node) {
        if (node.isLeaf())
            return (node.x + 20);
        else
            return rightMostPosn(node.getRightNode());
    }
 
    /**
     * @param node The root node of the tree
     * @return The height of the tree in the number of pixels.
     */
    public int treeHeight(Node node) {
        return (bottomMostPosn(node) - node.y);
    }
 
    /**
     * @param node The root node of the tree
     * @return The bottom most position of the tree
     */
    public int bottomMostPosn(Node node) {
	if (node == null) return 0;
        if (node.isLeaf())
            return (node.y + 30);
        else {
            int rightBottom = bottomMostPosn(node.getRightNode());
            int leftBottom = bottomMostPosn(node.getLeftNode());
            return (rightBottom > leftBottom ? rightBottom : leftBottom);
        }
    }

    /**
     * Drawing a leaf node of the heap.
     * @param g Graphical context
     * @param node The node to be drawn
     */
    public void drawLeafNode(Graphics g, Node node) {
        int x = node.x; int y = node.y;
        int weight = node.getWeight();
        if (node.highlight)
            g.setColor(Color.black);
        else
            g.setColor( Color.blue );
        g.fillRect(x, y, 20, 30);
	g.setColor(Color.black);
	g.drawRect(x, y, 20, 30);
	if (node.getLabel().length() > 0) {
	    g.setColor( Color.yellow );
	    g.setFont( hugeFont );
	    g.drawString(node.getLabel(), node.x + 5, node.y + 12);
	}
        g.setColor( Color.white );
	g.setFont( bigFont );
        g.drawString(""+node.getWeight(), node.x + 2, node.y+27);
    }

    /**
     * Draw a node of the array representation of the heap.
     * @param g Graphical context
     * @param x The x coordinate of the top left corner of the node
     * @param y The y coordinate of the top left corner of the node
     * @param node The node to be drawn
     */
    public void drawArrayNode(Graphics g, int x, int y, Node node) {
        int weight = node.getWeight();
        if (node.highlight)
            g.setColor(Color.black);
        else
            g.setColor( Color.red );
        g.fillRect(x, y, 20, 30);
	g.setColor(Color.black);
	g.drawRect(x, y, 20, 30);
        g.setFont(hugeFont);
        g.setColor( Color.yellow );
        g.drawString(""+weight, x+2, y+25);
    }

    /**
     * Drawing a node based on the input parameters.
     * @param g Graphical context
     * @param node The node to be drawn
     */
    public void drawNode(Graphics g, Node node) {
        if (node.highlight)
            g.setColor(Color.black);
        else
            g.setColor( darkgreen );
        g.fillRect(node.x, node.y, 20, 30);
	g.setColor(Color.black);
	g.drawRect(node.x, node.y, 20, 30);
	if (node.getLabel().length() > 0) {
	    g.setColor( Color.yellow );
	    g.setFont( hugeFont );
	    g.drawString(node.getLabel(), node.x + 5, node.y + 12);
	}
        g.setColor( Color.white );
	g.setFont( bigFont );
        g.drawString(""+node.getWeight(), node.x + 2, node.y+27);
 
        // draw links to children
	if (node.getLeftNode() != null) {
            g.setColor( Color.black );
            g.drawLine(node.x + 6, node.y + 30,
                node.getLeftNode().x + 10, node.getLeftNode().y);
	    if (node.highlightLeft) {
                g.drawLine(node.x + 5, node.y + 30,
                    node.getLeftNode().x + 9, node.getLeftNode().y);
                g.drawLine(node.x + 4, node.y + 30,
                    node.getLeftNode().x + 8, node.getLeftNode().y);
	    }
	}

	if (node.getRightNode() != null) {
	    g.setColor( Color.black );
            g.drawLine(node.x + 14, node.y + 30,
                node.getRightNode().x + 10, node.getRightNode().y);
	    if (node.highlightRight) {
                g.drawLine(node.x + 15, node.y + 30,
                    node.getRightNode().x + 11, node.getRightNode().y);
                g.drawLine(node.x + 16, node.y + 30,
                    node.getRightNode().x + 12, node.getRightNode().y);
	    }
	}
    }

    /**
     * Move the tree starting with node dx pixels to the right and dy
     * pixels down.
     * @param node The root node of the tree to be moved.
     * @param dx The change in x direction.
     * @param dy The change in y direction.
     */
    public void moveNode(Node node, int dx, int dy) {
	if (node == null) return;
        node.x += dx;
        node.y += dy;
        if (!node.isLeaf()) {
            moveNode(node.getLeftNode(), dx, dy);
            moveNode(node.getRightNode(), dx, dy);
        }
    }

    public void highlightNode(Node node) {
	node.highlight = true;
	if (node.getLeftNode() != null)
	    highlightNode(node.getLeftNode());
	if (node.getRightNode() != null)
	    highlightNode(node.getRightNode());
    }

    public void restoreNode(Node node) {
	node.highlight = false;
	if (node.getLeftNode() != null)
	    restoreNode(node.getLeftNode());
	if (node.getRightNode() != null)
	    restoreNode(node.getRightNode());
    }

    public Node getNodeAt(int posn) {
	Node posnNode = (Node)posnList.elementAt(posn-1);
	for (int i = 0; i < nodeList.size(); i++) {
	    Node node = (Node)nodeList.elementAt(i);
	    if (node.x == posnNode.x && node.y == posnNode.y) {
		return node;
	    }
	}
	return null;
    }

    public int sumNodeWeight(Node node) {
	if (node == null) return 0;
	return (sumNodeWeight(node.getRightNode()) + 
		sumNodeWeight(node.getLeftNode()) + 
		node.getWeight());
    }
}