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