递归计算树中的特殊节点

Question

我构建了一个由节点组成的树，每个节点都有一个属性和一个后继列表。我正在尝试实现一个递归函数，该函数开始遍历给定节点处的树（在此示例中为节点 "Method"）。该函数应计算具有给定属性的嵌套节点的数量。最后，我想 return 在单个分支中找到的最高数字。说到给定的例子，我想找到属性为 "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;
}

这种方法的问题在于它计算给定树中的所有循环，而不是仅仅返回嵌套分支的最大数量。因此，对于给定的示例，它不是 returning 3（这将是我想要的）它 returns 7 等于整棵树中 "Loops" 的总数。

显然，我在考虑递归方法时遇到了一些麻烦。有人可以帮助我吗？

Answer 1

private static int getLNDforMethod(DirectedNodeInterface curNode) {

    int maxChild = 0;
    NodeIterator successors = curNode.getSuccessors();
    while(successors.hasNext())
    {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();
        maxChild = Math.max(maxChild, getLNDforMethod(curSuc));
    }

    return maxChild + (isLoop(curNode) ? 1 : 0);
}

Answer 2

构思递归算法的一个非常好的策略是假设您已经实现了您的算法。在您的情况下，这意味着假设您已经有一个函数可以找到单个 path.Your 实现的 max 归结为为每个 child 调用函数（记住，我们假设它已经实现了），选择其中的最大值，然后 returning 那个最大值，或者 returning max 加一，如果我们当前的节点满足条件。

查找单条路径最大计数的算法如下：

将方法的 return 值 max 设置为 0
如果所需属性不存在，则将当前节点添加的值 own 设置为 0，如果当前节点中存在该属性，则设置为 1
为每个 child 调用 getLNDforMethod，得到 childMax
将max设置为max和own+childMax
Return 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;
}

Answer 3

您的问题是您在进行广度优先搜索时没有费心考虑您自己的问题陈述。您想要的是 LOOP 在任何分支中出现的最大次数，但您正在做的是计算整个树中 LOOP 的所有出现次数。您可以通过将广度优先搜索转换为深度优先搜索或仅返回子递归调用结果的最大值来解决此问题。

private static int GetLNDForMethod(DirectedNodeInterface curNode) {
    NodeIterator successors = curNode.getSuccessors();
    unsigned int numLnds = 0;
    while (successors.hasNext()) {
        successors.next();
        DirectedNodeInterface curSuc = (DirectedNodeInterface) successors.getNode();

        unsigned int curLnds = GetLNDForMethod(curSuc);
        if (isLoop(curSuc))
            curLnds++;
        if (numLnds < curLnds)
            numLnds = curLnds;
    }

    return numLnds;
}

我在这里所做的并不是对您的代码进行大量修改，我只是插入了另一个变量并检查它是否大于当前值，如果是则设置第一个。

请注意，由于你（和我）只考虑后继而不检查当前节点，因此如果根节点是 LOOP

，则此结果将比实际结果低一个

递归计算树中的特殊节点

Recursively counting special nodes in a tree

java

algorithm

tree

recursion

traversal