C ++获得树的最低级别

Question

我需要知道一棵树有多少叶子，但有一些条件。

所有 children 或叶子，将始终处于同一级别，但可以是级别 1,2,3,4,5 ...我不知道会是哪一个.所以你不能算 grandhildren + grandgrandchildren ...他们将处于同一水平并且将是他们中的较低者，在这种情况下：grandgrandchildren.
一定有一个节点没有叶子，但如果不是最底层的叶子，就不必算叶子。

我会尝试用一些例子来解释我自己。想象一下你有这棵树：

 A
 |- B
 |  |- B1
 |  |- B2                 Number of 'leafs' = 2 (B1 and B2). C doesn't count as it is in an 
 |                                                           upper level)
 |- C

另一个例子：

 A
 |- B
 |  |- B1
 |  |- B2                 Number of 'leafs' = 3 (B1,B2,D1)
 |
 |- C
 |- D
    |-D1

另一个例子：

 A
 |- B
 |  |- B1
 |  |   |-B11
 |  |- B2                 Number of 'leafs' = 1 (B11). D1 is not a leaf. It is a 'node' as 
 |                                    leafs in this case are in level 4 (counting A as 1)
 |- C
 |- D
    |-D1

我正在使用类似于 QTreeWidgetItem 的 C++ 和 Qt，所以我有一个 object（我们称它为 myTree，我可以这样问：myTree->childCount() 所以在第一个例子中，如果我调用它，它会说 2（B 和 C）并且对于每个我都可以重复该操作。

我试图计算所有给我 childcount() 但后来，它给了我 4（B，C，B1 和 B2）而不是我想要的 2（B1，B2）...这里我把我正在尝试的：

 int grandchild = 0;
   for (int i = 0; i < myTree->childCount( ); ++i)
   {
        Obj* child = myTree->child( i ); //Get the children. First time will be B and C
        if (child)
        {
          grandchild += p_child->childCount( ); // Here I wanted to get a total, for first example, I will get 3 which is not what I want 
        }
    }

提前致谢。

Answer 1

对于递归函数，您首先假设函数在节点上运行时，将 return 关于该节点的所有相关信息。然后每个节点只需要检查它的子节点和它自己来决定什么 return 到它上面的级别。

如果该节点没有子节点，则结果很简单：该节点有一个深度为 0 的最大深度节点（它本身）。

否则，最大深度等于其子节点中最大的最大深度+1，计数等于共享最大最大深度的所有子节点的计数之和。

#include <utility>
#include <vector>

struct node_type {
    std::vector<node_type*> children;
};

// returns the max depth between the node and all of its children
// along with the number of nodes at that depth
std::pair<int, int> max_depth_count(const node_type& node) {
    int depth = 0; // itself
    int count = 1; // itself

    for (const auto c : node.children) {
        auto [child_depth, child_count] = max_depth_count(*c);
        child_depth++;

        if (child_depth > depth) {
            depth = child_depth;
            count = child_count;
        }
        else if (child_depth == depth) {
            count += child_count;
        }
    }

    return {depth, count};
}

Answer 2

执行此操作的一种方法是执行广度优先遍历。这样你一层一层地访问，最后一个非空层的大小就是你需要的。

这样的广度优先遍历可以使用队列来完成。

以下是如何使用您在问题中提供的界面（Obj*、childCount、child）对其进行编码：

int n = 0; // number of nodes in the "current" level
if (myTree != nullptr) {
    std::queue<Obj*> q;
    q.push(myTree); // The first level just has the root
    while (q.size()) { // While the level is not empty...
        n = q.size(); // ...remember its size
        for (int i = 0; i < n; ++i) { // ...and replace this level with the next
            Obj* node = q.front();
            q.pop();
            int m = node->childCount();
            for (int j = 0; j < m; ++j) {
                q.push(node->child(j));
            }
        }
    }
}
std::cout << n << "\n";

C ++获得树的最低级别

C++ getting lowest level of a tree

c++

algorithm

tree

qt

qtreewidget