树的汇总
继上次浅谈了树的遍历之后，这次再浅谈一下树的汇总。此处的汇总是指将树中某节点的数据按指定的汇集到它的父节点中。例 如，可以将树节点中的数值累加到它的父节点中。仍如树的遍历一文，我将使用两种简单的算法，递归与和迭代，来实现这一功能。(2009.06.26最后更新)
1. 树节点
仍然沿用树的遍历一文中的TreeNode/GenericTreeNode，为便于阅读，将GenericTreeNode中的若干关键属性展示如下，
public class GenericTreeNode<T> implements TreeNode {
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;
}
递归法还是一如既往的简单易懂。与递归遍历树相比，递归汇总树的程序基本上没大的变化，我就不赘述了...
3. 迭代法
与迭代遍历树相比，迭代汇总树的程序有一些明显的变化。当初在思考迭代法时，有个问题一直困绕着我：如何将下级节点的值赋给它的父节点，并且父节点的值要 不断的进行累加。在JavaWorld@TW中提出这个问题之后，很快就得到了清晰的解答(真的很感谢社区里的大大们)。毫无疑问，用迭代法遍历一棵树时 需要使用一个栈，但同时，为了维护节点与汇总值之间的关系，还需要另一个栈进行辅助。具体程序如下所示，
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与它的汇总值一同置入一个栈(nodeValueStack)中，当节点N有子节点时，则将它的子节点及其汇总值也置入栈 中，节点N与它的子节点之间使用一个NULL值进行分隔；如果节点N是叶节点则累加汇总值；如果节点N为NULL，则表示子节点们的汇总已结束，
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;
}
}
在上述的汇总中，均只累加了叶节点中的数值，而不管分枝节点和根节点本身所拥有的数值。如果要累加这些节点本身的数值，应该如何做呢？大家自己做做看吧， 肯定非常简单 ^_^
4. 小结
树的汇总肯定是一个十分常见的应用，除了汇总数据之外，我们还可以汇集节点中的对象，如汇总挂载在节点上的集合对象中的元素，使得父节点能够拥有所有子节点所拥有的元素。上述方法的效率应该不算低，主要是因为所有的树节点只需要访问一次。