树的汇总
继上次浅谈了树的遍历之后，这次再浅谈一下树的汇总。此处的汇总是指将树中某个节点的数据按指定的规则汇集到它的父节点中。例如，可以将树节点中的数值累加到它的父节点中。仍如树的遍历一文，我将使用两种简单的算法，递归与和迭代，来实现这一功能。(2009.08.09最后更新)
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);
sumValue += bufNodeValueTuple.value;
} 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. 小结
树的汇总肯定是一个十分常见的应用，除了汇总数据之外，我们还可以汇集节点中的对象，如汇总挂载在节点上的集合对象中的元素，使得父节点能够拥有所有子节点所拥有的元素。上述方法的效率应该不算低，主要是因为所有的树节点只需要访问一次。