树的汇总

树的汇总2011-09-30 blogjava Jiangshachina继上次浅谈了树的遍历之后，这次再浅谈一下树的汇总。此处的汇总是指将树中某节点的数据按指定的汇集到它的父节点中。例如，可以将树节点中的数值累加到它的父节点中。仍如树的遍历一文，我将使用两种简单的算法，递归与和迭代，来实现这一功能。（2009.06.26最后更新）

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;
}

递归法还是一如既往的简单易懂。与递归遍历树相比，递归汇总树的程序基本上没大的变化，我就不赘述了...