java自定义二叉树续：Hoffman树和将数学算式建树

java自定义二叉树续：霍夫曼树和将数学算式建树
主要使用自己上一篇文章中的自定义二叉树类实现了霍夫曼树，霍夫曼编码和讲一个数学算式建成树。
  1.霍夫曼树和霍夫曼编码
  霍夫曼树即最优二叉树，因为它每个叶子结点到根结点的距离与叶子结点的权值有关，往往此权值越大，它的路径越短，即带权路径长度要保持最小，所以叫它最优二叉树。
 
  以下为代码：
  结点类的补充
 

private String code = " ";

	public String getCode() {
		return code;
	}

	public void setCode(String code) {
		this.code = code;
	}

  核心代码：
 

/**
	 * 按照传入的数组创建霍夫曼树的方法 通过优先队列实现
	 * 
	 * @param arr
	 *            传入的整型数组
	 */
	public void creatHuffmanTree(int[] arr) {

		if (arr == null) {
			throw new RuntimeException("空数组，无法建树");
		} else {
			// 创建优先队列对象
			PriorityQueue<TNode> que = new PriorityQueue<TNode>(arr.length,
					new MyComparator());
			// 将数组中的元素建立结点对象并加入到优先队列中去
			for (int i = 0; i < arr.length; i++) {
				TNode node = new TNode(arr[i]);
				que.add(node);
			}
			while (que.size() > 1) {
				// 将两个结点连成树
				TNode ltree = que.poll();
				TNode rtree = que.poll();
				TNode node = new TNode((Integer) ltree.getObj()
						+ (Integer) rtree.getObj());
				node.setLeft(ltree);
				node.setRight(rtree);
				ltree.setParent(node);
				rtree.setParent(node);

				// 加入子结点
				que.add(node);

			}
			root = que.poll();
		}

	}

	/**
	 * 打印此树的霍夫曼编码
	 * 
	 * @param node
	 *            由指定位置开始做为根结点
	 * 
	 */
	public void printHCode(TNode node) {
		if (node == null) {
			throw new RuntimeException("空树，无法编码！");
		} else {
			TNode current = node;
			if (current.getLeft() != null) {
				// 向左编码1
				current.getLeft().setCode(current.getCode() + '1');
				printHCode(current.getLeft());
				// 向右编码0
				current.getRight().setCode(current.getCode() + '0');
				printHCode(current.getRight());
			} else {
				System.out.println(current.getObj()+"的霍夫曼编码是: \t"+current.getCode());
			}
		}
	}

  2.将算术表达式建成树
  在这段代码中主要通过将原本的代码转换为逆波兰表达式，以去除括号，然后转换为波兰表达式(波兰表达式将运算符写在前面，操作数写在后面，便于建树),建成树。计算时只需要后序遍历就可以简单的计算这个数学算式。
  代码如下:
 

/**
	 * 将一个数学算式转化为一个树
	 * 
	 * @param s
	 *            此算式的字符串
	 */
	public void AFtoTree(String s) {
		Stack<Character> sta = new Stack<Character>();
		sta.push('#');
		char[] ch = new char[s.length() + 1];
		int j = 0;
		// 将中序表达式转化为逆波兰表达式
		for (int i = 0; i < s.length(); i++) {
			char cha = s.charAt(i);
			if (cha != '+' && cha != '-' && cha != '*' && cha != '/'
					&& cha != '(' && cha != ')') {
				ch[j++] = cha;
			} else if (cha == '(') {
				sta.push(cha);
			} else if (cha == ')') {
				char c = sta.pop();
				while (c != '(') {
					ch[j++] = c;
					c = sta.pop();
				}
			} else {
				char c = sta.peek();
				while (c == '*' || c == '/') {
					ch[j++] = sta.pop();
					c = sta.peek();
				}
				sta.push(cha);
			}
		}
		char c = sta.pop();
		while (c != '#') {
			ch[j++] = c;
			c = sta.pop();
		}
		// 将逆波兰转化为波兰表达式
		char[] temp = new char[j + 1];
		for (int i = 0; i < j; i++) {
			temp[j - i - 1] = ch[i];
		}
		temp[j] = '#';
		// 由波兰表达式建树
		root = creatAFTree(temp);
	}

	/**
	 * 将波兰表达式建成一棵树
	 * 
	 * @param ch
	 * @param key
	 * @return
	 */
	public TNode creatAFTree(char[] ch) {
		TNode current = null;
		if (ch[key] != '#') {
			if (ch[key] == '+' || ch[key] == '-' || ch[key] == '*'
					|| ch[key] == '/') {
				current = new TNode(ch[key++]);
				TNode temp = creatAFTree(ch);
				if (temp == null) {
				} else {
					current.setLeft(temp);
					temp.setParent(current);
				}
				TNode temp2 = creatAFTree(ch);
				if (temp2 == null) {
				} else {
					current.setRight(temp2);
					temp2.setParent(current);
				}
				return current;
			} else {
				current = new TNode(ch[key++]);
				return current;
			}
		} else {
			return null;
		}

	}