我构建了一个由节点组成的树,每个节点都有一个属性和一个后继列表。我正在尝试实现一个递归函数,该函数开始在给定节点(在本示例中为节点“ 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,它等于整个树中“循环”的总数。
显然,我在思考递归方法时遇到了一些麻烦。有谁能够帮我?
考虑递归算法的一个很好的策略是假设您已经实现了算法。在您的情况下,这意味着假设您已经有一个函数可以max
为单个路径查找。您的实现归结为为每个子代调用该函数(请记住,我们假设它已经实现),在其中选择最大值,然后返回该最大值,或者如果当前节点满足条件,则返回max加一。
查找单个路径的最大计数的算法如下:
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;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句