樹的匯總 用遞歸與和迭代來實現(xiàn)
繼上次淺談了樹的遍歷之后，這次再淺談一下樹的匯總。此處樹的匯總是指將樹中某節(jié)點的數(shù)據(jù)按指定的匯集到它的父節(jié)點中。例 如，可以將樹節(jié)點中的數(shù)值累加到它的父節(jié)點中。仍如樹的遍歷一文，我將使用兩種簡單的算法，遞歸與和迭代，來實現(xiàn)這一功能。
1. 樹節(jié)點
仍然沿用樹的遍歷一文中的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. 遞歸法
仍然先從最簡單的遞歸法開始，
- 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. 迭代法
與迭代遍歷樹相比，迭代匯總樹的程序有一些明顯的變化。當(dāng)初在思考迭代法時，有個問題一直困繞著我：如何將下級節(jié)點的值賦給它的父節(jié)點，并且父節(jié)點的值要 不斷的進(jìn)行累加。在JavaWorld@TW中提出這個問題之后，很快就得到了清晰的解答(真的很感謝社區(qū)里的大大們)。毫無疑問，用迭代法遍歷一棵樹時 需要使用一個棧，但同時，為了維護(hù)節(jié)點與匯總值之間的關(guān)系，還需要另一個棧進(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);
- 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());
- }
- }
- }
在遍歷樹的過程中，會將某節(jié)點N與它的匯總值一同置入一個棧(nodeValueStack)中，當(dāng)節(jié)點N有子節(jié)點時，則將它的子節(jié)點及其匯總值也置入棧 中，節(jié)點N與它的子節(jié)點之間使用一個NULL值進(jìn)行分隔；如果節(jié)點N是葉節(jié)點則累加匯總值；如果節(jié)點N為NULL，則表示子節(jié)點們的匯總已結(jié)束，
NodeValueTuple是一個二元組，用于維護(hù)節(jié)點與它的匯總值之間的關(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é)點中的數(shù)值，而不管分枝節(jié)點和根節(jié)點本身所擁有的數(shù)值。如果要累加這些節(jié)點本身的數(shù)值，應(yīng)該如何做呢？大家自己做做看吧， 肯定非常簡單 ^_^
4. 小結(jié)
樹的匯總肯定是一個十分常見的應(yīng)用，除了匯總數(shù)據(jù)之外，我們還可以匯集節(jié)點中的對象，如匯總掛載在節(jié)點上的集合對象中的元素，使得父節(jié)點能夠擁有所有子節(jié)點所擁有的元素。上述方法的效率應(yīng)該不算低，主要是因為所有的樹節(jié)點只需要訪問一次。
【編輯推薦】
