需求分析：
①输入树叶数
②输入树叶权值
③输出最优二元正则树的遍历
效果展示：
效果解说：
例如：“16（0）”，其中16是节点的权值，0是节点的层数。0层代表根节点
涉及类：
①TreeNodeMananger : 根据树叶的权值或者树叶节点计算根节点，遍历树（先根，中根，后根）
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.InputMismatchException;
/**
* 类树节点管理类
*
* @author Lance 2014-12-22
* @version 1.0
*/
public class TreeNodeManager {
//根据节点，获取根节点
public static TreeNode getRootNode(TreeNode[] nodes) {
//计算最优树
for(int i=0 ; i<nodes.length-1 ; i++) {
Arrays.sort(nodes);
// for(TreeNode node : nodes) { //调试代码
// if(node == null) continue;
// System.out.print(new BigDecimal(node.getNum()).toString()+" ");
// }
// System.out.println("\n--------------------");
//有序树
TreeNode parent =
new TreeNode(nodes[i],nodes[i].getNum()+nodes[i+1].getNum(),nodes[i+1]);
TreeNode zero = new TreeNode(null,null);
nodes[i] = zero;
nodes[i+1] = parent;
}
TreeNode rootNode = nodes[nodes.length-1];
return rootNode;
}
//根据树叶权值，获取根节点
public static TreeNode getRootNode(double[] num) {
TreeNode[] nodes = new TreeNode[num.length];
for(int i=0 ; i<num.length ; i++) {
nodes[i] = new TreeNode(null,num[i],null);
}
return getRootNode(nodes);
}
/** If successfully print node,return true; else false;
* 如果打印节点成功，返回true；否则返回false
*
* @param node Parent node
* @param level The level of node
*/
public static boolean printNodes(TreeNode node,int level,int model) throws InputMismatchException {
if(node==null) return false;
TreeNode leftChild = node.getLeftChild();
TreeNode rightChild = node.getRightChild();
// 先根次序遍历
if(model == TreeNodeConstants.BEFORE) {
System.out.print(new BigDecimal(node.getNum()).toString()+"("+level+") ");
printNodes(leftChild,level+1,model);
printNodes(rightChild,model);
}
//中根次序遍历
else if(model == TreeNodeConstants.MIDDLE) {
printNodes(leftChild,model);
System.out.print(new BigDecimal(node.getNum()).toString()+"("+level+") ");
printNodes(rightChild,model);
}
// 后根次序遍历
else if(model == TreeNodeConstants.AFTER) {
printNodes(leftChild,model);
System.out.print(new BigDecimal(node.getNum()).toString()+"("+level+") ");
}
else {
throw new InputMismatchException("错误遍历模式");
}
return true;
}
}
②TreeNodeConstants : 保存树节点遍历模式
<span style="font-size:18px;">/**
* 树节点遍历模式常量类
*
* @author Lance 2014-12-22
* @version 1.0
*/
interface TreeNodeConstants {
public static final int BEFORE = 0; //前根次序遍历
public static final int MIDDLE = 0; //中根次序遍历
public static final int AFTER = 0; //后根次序遍历
}</span>
③TreeNode : 保存了树节点信息
/**
* Class about tree node
* Implements the interface Comparable,in order to make it comparable
* 树节点类
* 实现了Comparable接口，使该类对象能够排序
*
* @author Lance 2014-12-22
* @version 1.0
*/
public class TreeNode implements Comparable<TreeNode> {
private double num = 0;
// private int level = 0; //层数
private TreeNode parent = null; //父节点
private TreeNode leftChild=null; //左子节点
private TreeNode rightChild=null; //右子节点
public TreeNode(TreeNode leftChild,double num,TreeNode rightChild) {
this.leftChild = leftChild;
this.num = num;
this.rightChild = rightChild;
}
//Order by num (根据num的数值排序)
@Override
public int compareTo(TreeNode t) {
return (int)Math.signum(this.getNum()-t.getNum());
}
public double getNum() {
return num;
}
public TreeNode getParent() {
return parent;
}
public TreeNode getLeftChild() {
return leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
}
④TreeDemo ： 效果演示
//最优二元树计算、以及遍历
import java.util.Scanner;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.math.BigDecimal;
public class TreeDemo {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//Input number of leaf (输入树叶数)
System.out.print("Input number of leaf(输入树叶数) : ");
int n = scan.nextInt();
if(n < 1) return ;
//Input data (输入树叶权值)
double[] num = new double[n];
System.out.print("Input data (输入树叶权值) : ");
for(int i=0 ; i<num.length ; i++) {
num[i] = scan.nextDouble();
}
// TreeNode[] nodes = new TreeNode[num.length]; //调试代码
// for(int i=0 ; i<num.length ; i++) {
// nodes[i] = new TreeNode(null,null);
// }
//Get root node (获取根节点)
// TreeNode rootNode = TreeNodeManager.getRootNode(nodes); //调试代码
TreeNode rootNode = TreeNodeManager.getRootNode(num);
//Print nodes (打印节点)
TreeNodeManager.printNodes(rootNode,TreeNodeConstants.MIDDLE);
// TreeNodePrinter.printNodes(rootNode,4); //调试代码
}
}
类功能说明：
①可单独使用TreeNodeManager的遍历功能，不限于二元正则树
②可根据TreeNodeConstants选择遍历的模式（先根次序遍历，中根，后根），依照需求选择
程序缺陷：
①使用了BigDecimal：容易造成额外的内存开支。
使用原因：美观
@author Lance 2014-12-22 20:20
