c++ - 将军树高度

Question

我正在做 Tamassia 和 Goodrich 的 C++ 数据结构和算法(第 2 版)

我无法理解一般树 T 高度的运行时间为 O(n + sum_over_p(1 + dp)) 其中 n 是 T 的节点数，dp 是节点 p 的深度(第 276 页) .

这里使用的概念是“树的高度是外部节点的最大深度”

这是书中给出的求树高的代码

int height1(const Tree& T) {
    int h = 0;
    PositionList nodes = T.positions(); // list of all nodes
    for (Iterator q = nodes.begin(); q != nodes.end(); ++q) { 
        if (q−>isExternal())
            h = max(h, depth(T, *q)); // get max depth among leaves
    }
    return h;
}

谢谢!!

更新

深度函数的代码是

int depth(const Tree& T, const Position& p) {
    if (p.isRoot())
        return 0; // root has depth 0
    else
        return 1 + depth(T, p.parent()); // 1 + (depth of parent)
}

Answer 1

按照我的理解，您遍历树中的所有节点是 O(n)。 对于每个外部节点，您调用 depth 函数，它采用 O(1+dp)(因为对于深度为 0 的根节点，它需要 1 次函数调用，因此是 1+dp)，所以这是sum_over_p(1 + dp) 的原因。

唯一的问题是，在代码中他们只为外部节点运行 depth 而在定义中他们似乎为每个节点调用它......所以我不确定哪里错了.