0

我有一棵树，其中有 3 个级别。有一个根节点，根节点有3个叶子节点，所有3个叶子节点都有3个其他叶子节点。节点代表服务器。现在，我必须计算给定级别的节点深度。深度计算如下：

1）如果服务器（节点）在任何级别和任何列“向上”，则该节点的深度为 0。

2) 如果服务器在最后一级并且“关闭”，则该节点的深度为无穷大。

3）对于所有其他情况，节点的深度是它的叶子节点的最大深度+1。最大深度是指在它的子节点中出现的多数值。

这里采用自下而上的方法，因此根节点的深度是级别 1 的深度。级别作为程序中的输入参数。现在，我必须计算根节点的深度。

我对程序做了一些假设：

1）查找子节点，跟随父节点的子指针。

2）要查找给定级别中的所有节点，请从根遍历子节点直到到达该级别并列出它们。

3) 根据给定的约束分配值。

我不确定我的方法是否正确。请帮帮我。谢谢你。

4

1 回答 1

0

我认为您想要以下伪代码的内容：

int nodeStatus(const Node& n) {
    int status = 0;
    if (n.isUp)
        return 1;
    else if (n.isLeaf)
        return -1;
    else {
        for (Node child : n.children) 
            status += nodeStatus(child);
    }
    if (status > 0)
        return 1;
    else
        return -1;
}

这是一种递归方法。它首先检查节点是否启动，在这种情况下它返回 1。然后如果节点关闭并且是叶子，它返回 -1，因为这是没有子节点的故障。最后，如果n是一个中间节点，那么它会为所有子节点再次递​​归调用此方法，并对结果求和。最后的if语句然后测试大多数孩子是否被归类为 1 或 -1 并相应地返回值。请注意，通过使用这些值1，-1可以将子节点相加并提供每个节点肯定有3（或奇数个）节点，那么永远不会status == 0出现没有多数情况的情况。

您将需要在某处定义一个struct被调用的Node对象，如下所示：

struct Node {
    Node(bool isUp, bool isLeaf);
    bool isUp;
    bool isLeaf;
    std::Vector<Node> children = new std::Vector<Node>(3);
}

我希望这能回答你的问题，但可能是我解释错了。

于 2013-11-11T14:29:44.363 回答