当前位置>>
树的汇总
继上次浅谈了树的遍历之后，这次再浅谈一下树的汇总。1. 树节点
仍然沿用树的遍历一文中的TreeNode/
public class GenericTreeNode<T> implements TreeNode {
private T userObject = null;
private TreeNode parent = null;
private List<GenericTreeNode<T>> children = new ArrayList<GenericTreeNode<T>>();
}
private T userObject = null;
private TreeNode parent = null;
private List<GenericTreeNode<T>> children = new ArrayList<GenericTreeNode<T>>();
}
2. 递归法
仍然先从最简单的递归法开始，
public static Double recursiveGatherValue(GenericTreeNode<Double> node) {
Double sumValue = null;
if (node.isLeaf()) {
return node.getUserObject();
} else {
sumValue = node.getUserObject();
List<GenericTreeNode<Double>> children = node.getChildren();
for (int i = 0, size = children.size(); i < size; i++) {
Double bufGatherValue = recursiveGatherValue(children.get(i));
sumValue += bufGatherValue;
}
}
node.setUserObject(sumValue);
return sumValue;
}
递归法还是一如既往的简单易懂。与递归遍历树相比，Double sumValue = null;
if (node.isLeaf()) {
return node.getUserObject();
} else {
sumValue = node.getUserObject();
List<GenericTreeNode<Double>> children = node.getChildren();
for (int i = 0, size = children.size(); i < size; i++) {
Double bufGatherValue = recursiveGatherValue(children.get(i));
sumValue += bufGatherValue;
}
}
node.setUserObject(sumValue);
return sumValue;
}
3. 迭代法
与迭代遍历树相比，迭代汇总树的程序有一些明显的变化。
public static void iterativeGatherValue(GenericTreeNode<Double> node) {
Stack<NodeValueTuple<Double>> nodeValueStack = new Stack<NodeValueTuple<Double>>();
Stack<GenericTreeNode<Double>> nodeStack = new Stack<GenericTreeNode<Double>>();
nodeStack.push(node);
Double sumValue = new Double(0.0D);
while (!nodeStack.isEmpty()) {
GenericTreeNode<Double> bufNode = nodeStack.pop();
if (bufNode == null) {
NodeValueTuple<Double> bufNodeValueTuple = nodeValueStack.pop();
bufNodeValueTuple.node.setUserObject(sumValue);
Double bufValue = bufNodeValueTuple.node.getUserObject();
sumValue += bufValue;
} else if (bufNode.isLeaf()) {
sumValue += bufNode.getUserObject();
} else {
nodeValueStack.add(new NodeValueTuple<Double>(bufNode, sumValue));
sumValue = new Double(0.0D);
nodeStack.push(null);
nodeStack.addAll(bufNode.getChildren());
}
}
}
在遍历树的过程中，会将某节点N与它的汇总值一同置入一个栈(Stack<NodeValueTuple<Double>> nodeValueStack = new Stack<NodeValueTuple<Double>>();
Stack<GenericTreeNode<Double>> nodeStack = new Stack<GenericTreeNode<Double>>();
nodeStack.push(node);
Double sumValue = new Double(0.0D);
while (!nodeStack.isEmpty()) {
GenericTreeNode<Double> bufNode = nodeStack.pop();
if (bufNode == null) {
NodeValueTuple<Double> bufNodeValueTuple = nodeValueStack.pop();
bufNodeValueTuple.node.setUserObject(sumValue);
Double bufValue = bufNodeValueTuple.node.getUserObject();
sumValue += bufValue;
} else if (bufNode.isLeaf()) {
sumValue += bufNode.getUserObject();
} else {
nodeValueStack.add(new NodeValueTuple<Double>(bufNode, sumValue));
sumValue = new Double(0.0D);
nodeStack.push(null);
nodeStack.addAll(bufNode.getChildren());
}
}
}
NodeValueTuple是一个二元组，
public class NodeValueTuple<V> {
public final GenericTreeNode<V> node;
public final V value;
public NodeValueTuple(GenericTreeNode<V> node, V value) {
this.node = node;
this.value = value;
}
}
在上述的汇总中，均只累加了叶节点中的数值，public final GenericTreeNode<V> node;
public final V value;
public NodeValueTuple(GenericTreeNode<V> node, V value) {
this.node = node;
this.value = value;
}
}
4. 小结
树的汇总肯定是一个十分常见的应用，除了汇总数据之外，
