樹(shù)的匯總 用遞歸與和迭代來(lái)實(shí)現(xiàn)
繼上次淺談了樹(shù)的遍歷之后，這次再淺談一下樹(shù)的匯總。此處樹(shù)的匯總是指將樹(shù)中某節(jié)點(diǎn)的數(shù)據(jù)按指定的匯集到它的父節(jié)點(diǎn)中。例 如，可以將樹(shù)節(jié)點(diǎn)中的數(shù)值累加到它的父節(jié)點(diǎn)中。仍如樹(shù)的遍歷一文，我將使用兩種簡(jiǎn)單的算法，遞歸與和迭代，來(lái)實(shí)現(xiàn)這一功能。
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);
- 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());
- }
- }
- }
在遍歷樹(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)一次。
【編輯推薦】
