递归计算树中的特殊节点

MRE:

我构建了一个由节点组成的树,每个节点都有一个属性和一个后继列表。我正在尝试实现一个递归函数,该函数开始在给定节点(在本示例中为节点“ Method”)处遍历树。该功能应计算具有给定属性的嵌套节点的数量。最后,我想返回单个分支中找到的最大数字。说到给定的示例,我想找到具有“ 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,它等于整个树中“循环”的总数。

显然,我在思考递归方法时遇到了一些麻烦。有谁能够帮我?

dasblinkenlight:

考虑递归算法的一个很好的策略是假设您已经实现了算法。在您的情况下,这意味着假设您已经有一个函数可以max为单个路径查找。您的实现归结为为每个子代调用该函数(请记住,我们假设它已经实现),在其中选择最大值,然后返回该最大值,或者如果当前节点满足条件,则返回max加一。

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

  • max方法的返回值设置0
  • 设置own,由当前节点添加的值,用于0缺少所需属性或1当前节点中是否存在该属性
  • 召集getLNDforMethod每个孩子,得到childMax
  • 设置max最大的maxown+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;
}

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章