btreeview.java

一个可以以图形方式直观表示的树状二叉树算法程序,可以实现生成和遍历.

package binarytreetravel;

import java.awt.*;
import javax.swing.*;
import java.util.*;
import java.awt.event.*;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class BTreeView extends JPanel implements
    Observer, Runnable{
  public final static int RADIUS = 5;    //在连接两个圆的
                                    //线段两头的小圆点的直径
  BLinkedTree blTree;//用inOrder()排列的树
                                    //的集合
  BTreeNode choiceNode;
  Graphics2D g2d;
  LinkedList orderList;
  Thread delay;

  public BTreeView() {
    super();
    this.setBackground(Color.white);

    //建立视图并显示
    BTreeNode root = new BTreeNode("");
    blTree = new BLinkedTree(root);

    try {
      jbInit();
    }
    catch(Exception e) {
      e.printStackTrace();
    }
  }
  private int caculateSize(int depth) {
    if(depth == 1) return 3;
    else return 2*caculateSize(depth-1)+1;
  }
  private void inOrderSetLocation(BTreeNode t, int first) {
    //动态确定各结点的位置
    BTreeNode current;
    if(first == 1) {
      BTreeNode rfather = new BTreeNode("");
      current = blTree.root;
      blTree.root.father = rfather;
      rfather.rect = new Rectangle(new Point(this.getWidth(),
                                             BTreeNode.RADIUS*2));
      blTree.root.rect = new Rectangle(this.getWidth()/2 -
                                       BTreeNode.RADIUS,
                                       BTreeNode.RADIUS*2,
                                       BTreeNode.RADIUS*2,
                                       BTreeNode.RADIUS*2);
      first = 0;
    }
    else current = t;

    if(current != null) {
      if (current.lchild != null)
        current.lchild.rect = new Rectangle(current.rect.x -
                                            Math.abs( (current.rect.x -
                                            current.father.rect.x) / 2),
                                            current.rect.y +
                                            6 * BTreeNode.RADIUS,
                                            BTreeNode.RADIUS * 2,
                                            BTreeNode.RADIUS * 2);
      if (current.rchild != null)
        current.rchild.rect = new Rectangle(current.rect.x +
                                            Math.abs( (current.rect.x -
                                            current.father.rect.x) / 2),
                                            current.rect.y +
                                            6 * BTreeNode.RADIUS,
                                            BTreeNode.RADIUS * 2,
                                            BTreeNode.RADIUS * 2);
      inOrderSetLocation(current.lchild, first);
      inOrderSetLocation(current.rchild, first);
    }
  }

  public void makeBTreeView() {
    //画出友好界面,方便查看
    int depth = blTree.depth(null, 1);
    //setPreferredSize(new Dimension(caculateSize(depth)*BTreeNode.RADIUS,
    //                              6*(depth+1)*BTreeNode.RADIUS));
    inOrderSetLocation(null, 1);

    LinkedList llist = blTree.preOrder(null, 1);
    Iterator iter = llist.iterator();
    while(iter.hasNext()) {
      BTreeNode btNode = (BTreeNode)iter.next();
      g2d.setColor(Color.black);
      g2d.drawOval(btNode.rect.x, btNode.rect.y,
                 btNode.rect.width, btNode.rect.height);
      if(choiceNode != null) {
        g2d.setColor(Color.cyan);
        g2d.fillOval(choiceNode.rect.x, choiceNode.rect.y,
                choiceNode.rect.width, choiceNode.rect.height);
      }
      //连接两个结点的线段
      if(btNode.lchild != null) {
        g2d.setColor(Color.green);
        g2d.fillOval(btNode.lchild.rect.x+BTreeNode.RADIUS-BTreeView.RADIUS,
                   btNode.lchild.rect.y-BTreeView.RADIUS,
                   BTreeView.RADIUS*2, BTreeView.RADIUS*2);
        g2d.fillOval(btNode.rect.x+BTreeNode.RADIUS-BTreeView.RADIUS,
                   btNode.rect.y+2*BTreeNode.RADIUS-BTreeView.RADIUS,
                   BTreeView.RADIUS*2, BTreeView.RADIUS*2);
        g2d.drawLine(btNode.rect.x+BTreeNode.RADIUS,
                   btNode.rect.y+BTreeNode.RADIUS*2,
                   btNode.lchild.rect.x+BTreeNode.RADIUS,
                   btNode.lchild.rect.y);
      }
      if(btNode.rchild != null) {
        g2d.setColor(Color.green);
        g2d.fillOval(btNode.rect.x+BTreeNode.RADIUS-BTreeView.RADIUS,
                   btNode.rect.y+2*BTreeNode.RADIUS-BTreeView.RADIUS,
                   BTreeView.RADIUS*2, BTreeView.RADIUS*2);
        g2d.fillOval(btNode.rchild.rect.x+BTreeNode.RADIUS-BTreeView.RADIUS,
                   btNode.rchild.rect.y-BTreeView.RADIUS,
                   BTreeView.RADIUS*2, BTreeView.RADIUS*2);
        g2d.drawLine(btNode.rect.x+BTreeNode.RADIUS,
                   btNode.rect.y+BTreeNode.RADIUS*2,
                   btNode.rchild.rect.x+BTreeNode.RADIUS,
                   btNode.rchild.rect.y);
      }
    }
  }

  public void paintComponent(Graphics g) {
    int depth = blTree.depth(null, 1);
    setPreferredSize(new Dimension(caculateSize(depth)*BTreeNode.RADIUS,
                                  6*(depth+1)*BTreeNode.RADIUS));
    g2d = (Graphics2D)g;
    super.paintComponent(g);
    makeBTreeView();
  }

  public void update(Observable thing, Object o) {
    repaint();
  }

  private void jbInit() throws Exception {
    this.addMouseListener(new BTreeView_this_mouseAdapter(this));
  }

  void this_mouseClicked(MouseEvent e) {
    Point p = e.getPoint();
    choiceNode = blTree.searchNode(p);
    if(choiceNode != null) {
      this.repaint();
    }
  }
  public void showOrderView(LinkedList list) {
    //动态显示遍历结果
    orderList = list;
    if(delay == null) {
      delay = new Thread(this);
    }
    try {
      delay.start();   }    catch(Exception e1) {e1.printStackTrace();}
  }

  public void run() {
    while (Thread.currentThread() == delay) {
      g2d = (Graphics2D)this.getGraphics();
      g2d.setColor(Color.red);
      if (orderList != null) {
        Iterator iter = orderList.iterator();
        while (iter.hasNext()) {
          BTreeNode bn = (BTreeNode) iter.next();

          g2d.fillOval(bn.rect.x, bn.rect.y,
                       bn.rect.width, bn.rect.height);
          try {
            Thread.currentThread().sleep(800); //延时...毫秒
          }
          catch (InterruptedException e) {}
        }
      }
    }
  }
}

class BTreeView_this_mouseAdapter extends java.awt.event.MouseAdapter {
  BTreeView adaptee;

  BTreeView_this_mouseAdapter(BTreeView adaptee) {
    this.adaptee = adaptee;
  }
  public void mouseClicked(MouseEvent e) {
    adaptee.this_mouseClicked(e);
  }
}