樹(shù)的匯總
繼上次淺談了樹(shù)的遍歷之后，這次再淺談一下樹(shù)的匯總。此處的匯總是指將樹(shù)中某個(gè)節(jié)點(diǎn)的數(shù)據(jù)按指定的規(guī)則匯集到它的父節(jié)點(diǎn)中。例如，可以將樹(shù)節(jié)點(diǎn)中的數(shù)值累加到它的父節(jié)點(diǎn)中。仍如樹(shù)的遍歷一文，我將使用兩種簡(jiǎn)單的算法，遞歸與和迭代，來(lái)實(shí)現(xiàn)這一功能。(2009.08.09最后更新)
1. 樹(shù)節(jié)點(diǎn)
仍然沿用樹(shù)的遍歷一文中的TreeNode/GenericTreeNode，為便于閱讀，將GenericTreeNode中的若干關(guān)鍵屬性展示如下，
public class GenericTreeNode<T> implements TreeNode {
private T userObject = null;
private TreeNode parent = null;
private List<GenericTreeNode<T>> children = new ArrayList<GenericTreeNode<T>>();
}
2. 遞歸法
仍然先從最簡(jiǎn)單的遞歸法開(kāi)始，
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;
}
遞歸法還是一如既往的簡(jiǎn)單易懂。與遞歸遍歷樹(shù)相比，遞歸匯總樹(shù)的程序基本上沒(méi)大的變化，我就不贅述了...
3. 迭代法
與迭代遍歷樹(shù)相比，迭代匯總樹(shù)的程序有一些明顯的變化。當(dāng)初在思考迭代法時(shí)，有個(gè)問(wèn)題一直困繞著我：如何將下級(jí)節(jié)點(diǎn)的值賦給它的父節(jié)點(diǎn)，并且父節(jié)點(diǎn)的值要不斷的進(jìn)行累加。在JavaWorld@TW中提出這個(gè)問(wèn)題之后，很快就得到了清晰的解答(真的很感謝社區(qū)里的大大們)。毫無(wú)疑問(wèn)，用迭代法遍歷一棵樹(shù)時(shí)需要使用一個(gè)棧，但同時(shí)，為了維護(hù)節(jié)點(diǎn)與匯總值之間的關(guān)系，還需要另一個(gè)棧進(jìn)行輔助。具體程序如下所示，
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());
}
}
}
在遍歷樹(shù)的過(guò)程中，會(huì)將某節(jié)點(diǎn)N與它的匯總值一同置入一個(gè)棧(nodeValueStack)中，當(dāng)節(jié)點(diǎn)N有子節(jié)點(diǎn)時(shí)，則將它的子節(jié)點(diǎn)及其匯總值也置入棧中，節(jié)點(diǎn)N與它的子節(jié)點(diǎn)之間使用一個(gè)NULL值進(jìn)行分隔；如果節(jié)點(diǎn)N是葉節(jié)點(diǎn)則累加匯總值；如果節(jié)點(diǎn)N為NULL，則表示子節(jié)點(diǎn)們的匯總已結(jié)束。
NodeValueTuple是一個(gè)二元組，用于維護(hù)節(jié)點(diǎn)與它的匯總值之間的關(guān)系，代碼如下所示，
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;
}
}
在上述的匯總中，均只累加了葉節(jié)點(diǎn)中的數(shù)值，而不管分枝節(jié)點(diǎn)和根節(jié)點(diǎn)本身所擁有的數(shù)值。如果要累加這些節(jié)點(diǎn)本身的數(shù)值，應(yīng)該如何做呢？大家自己做做看吧，肯定非常簡(jiǎn)單 ^_^
4. 小結(jié)
樹(shù)的匯總肯定是一個(gè)十分常見(jiàn)的應(yīng)用，除了匯總數(shù)據(jù)之外，我們還可以匯集節(jié)點(diǎn)中的對(duì)象，如匯總掛載在節(jié)點(diǎn)上的集合對(duì)象中的元素，使得父節(jié)點(diǎn)能夠擁有所有子節(jié)點(diǎn)所擁有的元素。上述方法的效率應(yīng)該不算低，主要是因?yàn)樗械臉?shù)節(jié)點(diǎn)只需要訪問(wèn)一次。