递归计算树中的特殊节点

Question

我构建了一个由节点组成的树,每个节点都有一个属性和一个后继列表.我试图实现一个递归函数,它开始遍历给定节点的树(在这个例子中,在节点"方法").该函数应计算具有给定属性的嵌套节点的数量.最后,我想返回一个分支中找到的最高编号.说到给定的例子,我想找到具有属性"Loop"的最大嵌套节点数量,该属性为3(相应的分支标记为橙色).

例: 目前,我的方法如下:

private static int getLNDforMethod(DirectedNodeInterface curNode, int currentLND) {

    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext())
    {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();

        // isLoop returns true if the given node is a loop
        if(isLoop(curSuc))
        {
            ++currentLND;
        }

        currentLND = getLNDforMethod(curSuc, currentLND);
    }

    return currentLND;
}

这种方法的问题在于它计算给定树中的所有循环,而不是仅仅返回嵌套分支的最大数量.因此,不是返回3(这将是我想要的),而是返回给定示例的7,它等于整个树中"循环"的总数.

显然,我在考虑递归方法时遇到了一些麻烦.有谁能够帮我？

Answer 1

考虑递归算法的一个非常好的策略是假设您已经实现了算法.你的情况而言,这意味着假设您已经有发现的功能max单个path.Your实施归结为调用函数为每个孩子(记住,我们假设它已经实现),选择其中最大,如果当前节点满足条件,则返回最大值,或返回max加1.

查找单个路径的最大计数的算法如下:

• 将max方法的返回值设置为0
• 设置own当前节点添加的值,0如果不存在所需属性,或者1当前节点中是否存在该属性
• 呼唤getLNDforMethod每个孩子,并得到childMax
• 设置max最大的max和own+childMax
• 返回 max

这在Java代码中更容易表达:

private static int getLNDforMethod(DirectedNodeInterface curNode) {
    int max = 0;
    int own = isLoop(curNode) ? 1 : 0;
    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext()) {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();
        max = Math.max(max, own + getLNDforMethod(curSuc));
    }
    return max;
}