递归计算树中特定节点数

Question

我建立了一个树形结构，其中每个节点都有一个属性和一个后继节点列表。我正在尝试实现一个递归函数，从给定的节点开始遍历树（在此例中为节点“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;
}

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

显然，我在递归方法方面遇到了一些问题。有人能帮帮我吗？

- MRE

---

如果你需要最大值，我希望在方法的开头看到 int currentMax = 0，并且在后继循环中看到 currentMax = Math.max(currentMax,getLND...。 - OldCurmudgeon

Answer 1

一个思考递归算法的好策略是假设你已经实现了你的算法。在你的情况下，这意味着假设你已经有一个函数来找到单个路径的max。你的实现 boils down to calling the function for each child (remember, we're assuming it's already implemented), picking the max among them, and then either returning that max, or returning max plus one if our current node satisfies the condition.

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

• 将方法的返回值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;
}

- Sergey Kalinichenko

Answer 2

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

- DAle

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

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

请注意，由于你（和我）只考虑后继节点而不检查当前节点，因此如果根节点是循环，则此结果将比实际结果低一级。

- Woody1193