樹的匯總
繼上次淺談了樹的遍歷之后，這次再淺談一下樹的匯總。此處的匯總是指將樹中某個節點的數據按指定的規則匯集到它的父節點中。例如，可以將樹節點中的數值累加到它的父節點中。仍如樹的遍歷一文，我將使用兩種簡單的算法，遞歸與和迭代，來實現這一功能。(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. 小結
樹的匯總肯定是一個十分常見的應用，除了匯總數據之外，我們還可以匯集節點中的對象，如匯總掛載在節點上的集合對象中的元素，使得父節點能夠擁有所有子節點所擁有的元素。上述方法的效率應該不算低，主要是因為所有的樹節點只需要訪問一次。