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

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

引用

　　（1）设给定的一组权值为{W1，W2，W3，……Wn}，据此生成森林F={T1，T2，T3，……Tn},F 中的每棵二叉树只有一个带权为Wi的根节点（i=1，2，……n）。
  算法思想为：
　　（2）在F中选取两棵根节点的权值最小和次小的二叉树作为左右构造一棵新的二叉树，新二叉树根节点的权值为其左、右子树根节点的权值之和。
　　（3）在F中删除这两棵最小和次小的二叉树，同时将新生成的二叉树并入森林中。
　　（4）重复（2）（3）过程直到F中只有一棵二叉树为止。

  以下为代码：
  结点类的补充
 

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;
		}

	}