关于Swing打印二叉树

[img][/img]最近研究二叉树一类的树结构，总用调试的办法去搞好麻烦，想用界面显示树结构，想看是不是AVL啊，（红黑树那个还在弄，太麻烦），于是就想弄出界面来，考虑了下准备用flex做也网页图形的，毕竟研究过用flex绘图等简单的东西，又想想swing这东西还一直没弄过呢，学java的不会swing惭愧啊，就是今天给按钮加个点击事件都纠结了半天。。。。唉 性格所致 ，越是不会的东西越要去折腾。反正也是做的玩玩，于是就用swing去折腾，虽然我从没用过，但我想还不是一个绘图类画画直线啥的。

关于绘制树的思路：从最简单的二叉树搞起。每个节点增加坐标属性(x,y)，然后 遍历树的话也就是那4种遍历方法。前序、中序、后序、层次，或许有其他的遍历方法，目前只知道这几种简单的方法来遍历树。

下面上代码，代码写的很随意，未整理。

package sunfa.tree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class TreeXY<K, V> {
	public static void main(String[] args) {
		TreeXY<String, Object> tree = new TreeXY<String, Object>(null,
				new BaseXY(600, 0, 20, 10));
		int n = 10;
		Random ran = new Random();
		for (int i = 0; i < n; i++) {
			int o = ran.nextInt(100);
			System.out.print(o + ",");
			tree.put(Integer.toString(o), o);
		}
		System.out.println("printTree:");
		tree.printTree(tree.root);
	}

	private Comparator<K> comp;
	private Entry<K, V> root;
	private BaseXY baseXY;

	public TreeXY(Comparator<K> c, BaseXY baseXY) {
		if (c != null)
			comp = c;
		this.baseXY = baseXY;
	}

	public Entry<K, V> getRoot() {
		return root;
	}

	private List<Entry<K, V>> equalsXY = new ArrayList<Entry<K, V>>();
	private Set<String> xyHash = new HashSet<String>();

	public void printTree(Entry<K, V> node) {
		if (node == null)
			return;
		printTree(node.left);
		System.out.print(node.key+",");// + "[" + node.xy + "],");
		String key = node.xy.x + "_" + node.xy.y;
		if (xyHash.contains(key)) {
			equalsXY.add(node);
		} else {
			xyHash.add(key);
		}
		printTree(node.right);
	}

	public void put(K key, V value) {
		if (root == null) {
			root = new Entry<K, V>(key, value, new XYPosition(baseXY.rootX,
					baseXY.rootY), null);
			return;
		}
		Entry<K, V> node = root;
		while (true) {
			int n = compare(key, node.key);
			if (n == 0) {
				node.value = value;
				return;
			} else if (n < 0) {
				if (node.left != null) {
					node = node.left;
				} else {
					node.left = new Entry<K, V>(key, value, new XYPosition(
							node.xy.x - baseXY.xgap, node.xy.y + baseXY.ygap),
							node);
					return;
				}
			} else {
				if (node.right != null) {
					node = node.right;
				} else {
					node.right = new Entry<K, V>(key, value, new XYPosition(
							node.xy.x + baseXY.xgap, node.xy.y + baseXY.ygap),
							node);
					return;
				}
			}
		}
	}

	private int compare(K k1, K k2) {
		return comp != null ? (comp.compare(k1, k2)) : (((Comparable<K>) k1)
				.compareTo(k2));
	}

	public static class Entry<K, V> {
		public Entry<K, V> parent;
		public Entry<K, V> left;
		public Entry<K, V> right;
		public XYPosition xy;
		public K key;
		public V value;

		public Entry(K key, V value, XYPosition xy, Entry<K, V> parent) {
			super();
			this.key = key;
			this.value = value;
			this.xy = xy;
			this.parent = parent;
		}
	}

	public static class XYPosition {
		public int x;
		public int y;

		public XYPosition(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return this.x + "," + this.y;
		}
	}
}

上面是一颗简单的二叉树，节点含有坐标属性。

package sunfa.tree;

public class BaseXY {
	int rootX;// 根节点的X
	int rootY;// 根节点的Y
	// int size;// 单元格子大小

	// 水平和垂直间距
	int xgap;
	int ygap;

	public BaseXY(int rootX, int rootY, int xgap, int ygap) {
		super();
		this.rootX = rootX;
		this.rootY = rootY;
		this.xgap = xgap;
		this.ygap = ygap;
	}

}

这个是初始化树的时候传递的基础坐标和间距的类。

package sunfa.tree.draw;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Container;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.font.FontRenderContext;
import java.awt.font.TextLayout;
import java.awt.geom.Line2D;
import java.awt.geom.RoundRectangle2D;
import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Queue;
import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

import sunfa.tree.BaseXY;
import sunfa.tree.TreeXY;
import sunfa.tree.TreeXY.Entry;

public class GrapDemo1 extends JFrame implements ActionListener {
	private static final long serialVersionUID = 1L;
	JButton btn1;
	Container c;

	public GrapDemo1() {
		super("map");
		c = getContentPane();
		setSize(1000, 600);
		MapPanel comp = new MapPanel();
		comp.setSize(400, 400);
		btn1 = new JButton("text");
		btn1.setSize(100, 30);
		// btn1.action(MouseEvent.MOUSE_CLICKED, this);
		btn1.addActionListener(this); // 注册bt的监听者对象this
		getContentPane().add(btn1);
		getContentPane().add(comp);
	}

	public static void main(String[] args) {
		GrapDemo1 frame = new GrapDemo1();
		frame.setVisible(true);
	}

	public void actionPerformed(ActionEvent e) {
		if (e.getSource() == btn1) {
			Random ran = new Random();
			btn1.setText("btn1" + ran.nextInt(111));
			MapPanel comp = new MapPanel();
			comp.setSize(400, 400);
			c.add(comp);
		}
	}
}

class MapPanel extends JPanel {
	private static final long serialVersionUID = 1L;

	@Override
	protected void paintComponent(Graphics g) {
		// test(g);
		Graphics2D grap = (Graphics2D) g;// 绘图对象
		grap.clearRect(0, 0, 400, 400);
		// drawGrid(grap);

		// DrawTree();
		// render(400, 400, grap);
		DrawTree(grap);
	}

	private void DrawTree(Graphics2D grap) {
		BufferedImage srcImg = new BufferedImage(800, 800,
				BufferedImage.TYPE_INT_RGB);
		Graphics2D imageG2 = srcImg.createGraphics();
		String text = "aa";
		Font font = new Font("宋体", Font.BOLD, 28);
		FontRenderContext frc = grap.getFontRenderContext();
		TextLayout tl = new TextLayout(text, font, frc);

		// 设置白底黑字
		imageG2.setBackground(Color.WHITE);
		imageG2.clearRect(0, 0, 800, 800);
		imageG2.setColor(Color.BLACK);

		TreeXY<Integer, Object> tree = new TreeXY<Integer, Object>(
				new Comparator<Integer>() {
					public int compare(Integer o1, Integer o2) {
						return o1 - o2;
					}
				}, new BaseXY(400, 30, 100, 40));
		int n = 50;
		list.clear();
		list2.clear();
		Random ran = new Random();
		for (int i = 0; i < n; i++) {
			int o = ran.nextInt(100);
			System.out.print(o + ",");
			tree.put(o, o);
		}
		System.out.println("printTree:");
		// tree.printTree(tree.getRoot());
		// drawTree(grap);
		printTree(tree.getRoot(), imageG2);

		String ss = "";
		for (int i = 0; i < list2.size(); i++) {
			ss += list2.get(i).toString() + ",";
		}
		imageG2.drawString(ss, 10, 20);

		tl.draw(imageG2, 0, 0);
		grap.drawImage(srcImg, 100, 10, srcImg.getWidth(), srcImg.getHeight(),
				null);
	}

	public void render(int w, int h, Graphics2D g2) {
		BufferedImage srcImg = new BufferedImage(w, h,
				BufferedImage.TYPE_INT_RGB);
		Graphics2D imageG2 = srcImg.createGraphics();

		// 设置白底黑字
		imageG2.setBackground(Color.RED);
		imageG2.clearRect(0, 0, w, h);
		imageG2.setColor(Color.BLACK);

		String text = "标题：订货单位";
		Font font = new Font("宋体", Font.BOLD, 28);
		FontRenderContext frc = g2.getFontRenderContext();
		TextLayout tl = new TextLayout(text, font, frc);
		tl.draw(imageG2, 50, 50);

		// 文字的宽度将压缩一半显示
		g2.drawImage(srcImg, 0, 0, srcImg.getWidth() / 2, srcImg.getHeight(),
				null);
		// 文字正常显示
		g2.drawImage(srcImg, 0, srcImg.getHeight(), srcImg.getWidth(),
				srcImg.getHeight(), null);
	}

	int n = 10;

	private void drawTree(Graphics2D grap) {
		if (n == 0) {
			return;
		}
		grap.drawArc(100, 200, 110, 110, 0, 360);
		n--;
		drawTree(grap);
	}

	// private List<TreeXY.Entry> equalsXY = new ArrayList<TreeXY.Entry>();
	// private Set<String> xyHash = new HashSet<String>();
	private List<String> list = new ArrayList<String>();
	private List<String> list2 = new ArrayList<String>();

	// 中序周游打印二叉树
	public void printTree(TreeXY.Entry node, Graphics2D grap) {
		if (node == null)
			return;
		printTree(node.left, grap);
		// ---------start
		String key = node.xy.x + "_" + node.xy.y;
		int r = 30;
		// int tmp = node.xy.x - r;
		boolean isExits = false;
		for (int i = 0; i < list.size(); i++) {
			if (list.get(i).toString().equals(key)) {
				isExits = true;
			}
		}
		if (isExits) {
			// node.xy.x += 40;
			// tmp += 20;
			System.out.print("存在：" + key + ",");
		} else {
			list.add(key);
		}
		// if (xyHash.contains(key)) {
		// // equalsXY.add(node);
		// node.xy.x +=40;
		// tmp += 20;
		// System.out.print("存在："+key+",");
		// } else {
		// xyHash.add(key);
		// }
		int circleX = node.xy.x + r / 2 - 5;// 圆心
		int circleY = node.xy.y + r / 2 + 5;
		grap.drawArc(node.xy.x, node.xy.y, r, r, 0, 360);
		grap.drawString(node.key.toString(), circleX, circleY);
		if (node.parent != null) {
			int circleX2 = node.parent.xy.x + r - 5;
			int circleY2 = node.parent.xy.y + r + -5 - r / 2;
			grap.drawLine(circleX2, circleY2, circleX, circleY);
		}
		System.out.print(node.key + "[" + node.xy + "],");
		list2.add(node.key.toString());
		// -------------end
		printTree(node.right, grap);
	}

	private Queue<TreeXY.Entry> queue = new ArrayBlockingQueue<TreeXY.Entry>(10);

	// 层次打印二叉树
	public void printTree2(TreeXY.Entry node, Graphics2D grap) {
		queue.offer(node);
		while (queue.size() > 0) {
			node = queue.poll();
			if (node == null) {
				System.out.println("结束");
				return;
			}
			String key = node.xy.x + "_" + node.xy.y;
			int r = 30;
			// int tmp = node.xy.x - r;
			boolean isExits = false;
			for (int i = 0; i < list.size(); i++) {
				if (list.get(i).toString().equals(key)) {
					isExits = true;
				}
			}
			if (isExits) {
				node.xy.x += 40;
				// tmp += 20;
				System.out.print("存在：" + key + ",");
			} else {
				list.add(key);
			}
			int circleX = node.xy.x + r / 2 - 5;// 圆心
			int circleY = node.xy.y + r / 2 + 5;
			grap.drawArc(node.xy.x, node.xy.y, r, r, 0, 360);
			grap.drawString(node.key.toString(), circleX, circleY);
			if (node.parent != null) {
				int circleX2 = node.parent.xy.x + r - 5;
				int circleY2 = node.parent.xy.y + r + -5 - r / 2;
				grap.drawLine(circleX2, circleY2, circleX, circleY);
			}
			if (node.left != null)
				queue.offer(node.left);
			if (node.right != null)
				queue.offer(node.right);
		}
	}

	private void printTree2_0(ArrayBlockingQueue<TreeXY.Entry> queue,
			Graphics2D grap) {
		while (queue.size() > 0) {
			Entry o = queue.poll();
			if (o == null) {
				break;
			}
			if (o.left != null)
				queue.offer(o.left);
			if (o.right != null)
				queue.offer(o.right);
		}
	}

	// 绘制表格
	private void drawGrid(Graphics grap) {
		// grap = (Graphics2D) g;// 绘图对象
		int x1 = 0, y1 = 0, x2 = 0, y2 = 0, size = 40, row = 14, col = 17;
		int x3 = 0, y3 = 0;// 圆的坐标
		for (int i = 0; i < row; i++) {
			grap.drawLine(x1, y1, (col - 1) * size, y1);

			x3 = x1 + size >>> 1;
			y3 = y1 + size - (size >>> 1);
			grap.drawString((x1 + size >>> 1) + ","
					+ (y1 + size - (size >>> 1)), x3, y3);

			// 绘制的圆是按坐标点绘制弧形成圆的，无法得到圆心坐标点...
			grap.drawArc(x3, y3, size, size, 0, 360);
			y1 += size;
		}
		y1 = 0;
		for (int i = 0; i < col; i++) {
			grap.drawLine(x1, y1, x1, (row - 1) * size);
			x1 += size;
		}

		System.out.println("grap:" + grap);
	}

	// 学习笔记
	private void test(Graphics g) {
		Graphics2D grap = (Graphics2D) g;// 绘图对象
		grap.setPaint(new Color(255));// 设置绘图颜色
		grap.setStroke(new BasicStroke(15));// 设置笔的粗细

		// 在指定坐标处写文字
		grap.drawString("java绘图", 40, 240);
		// 线条
		Line2D.Float line = new Line2D.Float(100.0f, 100.0f, 200.0f, 200.0f);
		grap.draw(line);// 所有的图形都需要添加到绘图对象中才能显示到界面上

		// 矩形
		RoundRectangle2D.Double round = new RoundRectangle2D.Double(150, 140,
				100, 100, 1f, 1f);
		grap.setStroke(new BasicStroke(2));
		grap.draw(round);

		grap.setStroke(new BasicStroke(10));
		// 绘制一个覆盖指定矩形的圆弧或椭圆弧边框。 弧度可以指定从0-360,那么这就是一个圆
		grap.drawArc(20, 20, 20, 20, 0, 360);
		// 调用继承于Graphics类的方法绘制基本的图形，比如直线、矩形区域等
		grap.drawLine(10, 10, 120, 20);
	}
}

这个是绘制二叉树的绘图类，绘图类的代码比较乱没整理，现在也懒得去整理了，因为遇到了一个问题，纠结之。

这张图就是最后绘制出来的效果，很遗憾的是存在交叉的地方，重叠了。虽然想了好几种方法去解决，但都没有好的效果，一下午的时间就在那折腾这个，还好没啥子任务要做。

关于交叉部分的处理办法：
方法一：打印的时候处理。尝试过，效果差还很麻烦，并且和打印的代码混到了一起以后不好分离出来。
方法二：添加节点的时候处理。成功添加一个节点后，拿新添加的节点和其他所有的节点的坐标比较(可以把树的节点左边放到一个hashmap中，这里就直接get了，不用遍历树了)，如果存在重叠，这个时候注意观察，怎样才能让他们不重叠呢？办法其实很简单，先搞清楚新添加的节点相对于根节点而言是在根节点的左边还是在根节点的右边。如果是在根节点的左边就使根节点的左子节点向左移动(右边就使根节点的右子节点向右移动)，具体平移多少，示打印效果而定，可以平移一个单位或二个单位等等。

写这篇文章的时候我就在想，要不要使根节点的孙子节点也做对应的移动？还是不需要了，如果树的层次多的话，电脑的屏幕也装不下，也就失去了意义了，一般10来个层的树也就比较大了。所以使根节点的左右子树平移已经能满足基本的需求了。

或许也可以做成类似于企业人员结构图的形式。

未完。。。