C++ Qt 统计树结构最深层级符合规则的叶子节点数量

你之前的实现仅统计了根节点第一层子节点的子节点总数，既没有递归遍历所有层级，也没有先确定整棵树的最大深度，无法匹配你要求的「仅统计最深层级节点」的规则。

你需要先确定整棵树的最大深度，再统计所有处于该深度的节点总数，即可得到有效叶子数。这里提供两种实现方式：

递归实现（逻辑简单易读） #

首先实现两个工具函数：

1. 计算树的最大深度

// 入参：当前节点、当前节点所处层级（根节点传入1）
int getMaxDepth(QTreeWidgetItem* node, int currentLevel) {
    if (node->childCount() == 0) {
        return currentLevel;
    }
    int maxDepth = currentLevel;
    for (int i = 0; i < node->childCount(); ++i) {
        int childDepth = getMaxDepth(node->child(i), currentLevel + 1);
        maxDepth = qMax(maxDepth, childDepth);
    }
    return maxDepth;
}

2. 统计指定深度的节点数量

int countNodesAtDepth(QTreeWidgetItem* node, int currentLevel, int targetDepth) {
    if (currentLevel == targetDepth) {
        return 1;
    }
    if (node->childCount() == 0) {
        return 0;
    }
    int count = 0;
    for (int i = 0; i < node->childCount(); ++i) {
        count += countNodesAtDepth(node->child(i), currentLevel + 1, targetDepth);
    }
    return count;
}

调用方式：

// 假设根节点为root，根节点层级为1
int maxDepth = getMaxDepth(root, 1);
int validLeafCount = countNodesAtDepth(root, 1, maxDepth);

广度优先遍历实现（性能更优，避免递归栈溢出） #

仅需一次遍历即可得到结果，适合节点层级深、数量多的场景：

#include <QQueue>
#include <QMap>

int countDeepestLeaves(QTreeWidgetItem* root) {
    if (!root) return 0;
    QMap<int, int> levelNodeCount;
    QQueue<QPair<QTreeWidgetItem*, int>> traverseQueue;
    // 根节点入队，层级设为1
    traverseQueue.enqueue(qMakePair(root, 1));

    while (!traverseQueue.isEmpty()) {
        auto current = traverseQueue.dequeue();
        QTreeWidgetItem* currentNode = current.first;
        int currentLevel = current.second;
        // 记录当前层级的节点数
        levelNodeCount[currentLevel]++;
        // 子节点入队
        for (int i = 0; i < currentNode->childCount(); ++i) {
            traverseQueue.enqueue(qMakePair(currentNode->child(i), currentLevel + 1));
        }
    }
    // 返回最大层级对应的节点数
    return levelNodeCount.last();
}

调用方式：

int validLeafCount = countDeepestLeaves(root);

上述代码完全匹配你给出的三个示例：

• 示例1返回2，符合预期
• 示例2返回3，符合预期
• 示例3返回1，符合预期

内容的提问来源于stack exchange，提问作者Megasa3