c++中如何求二叉树节点个数_c++二叉树节点数量统计方法-C++-PHP中文网

c++中如何求二叉树节点个数_c++二叉树节点数量统计方法

裘德小鎮的故事

发布： 2025-09-26 10:44:01

原创

727人浏览过

答案是递归法最常用，定义TreeNode结构后，通过判断根节点是否为空，返回1加左右子树节点数之和，实现简洁高效。

c++中如何求二叉树节点个数_c++二叉树节点数量统计方法

在C++中统计二叉树的节点个数，最常用的方法是通过递归遍历整棵树。只要每个节点都被访问一次，就可以准确计数。

使用递归方式统计节点数量

从根节点开始，每遇到一个节点就加1，然后递归计算左子树和右子树的节点数之和。

定义二叉树节点结构：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

登录后复制

统计节点个数的递归函数：

立即学习“C++免费学习笔记（深入）”；

int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

登录后复制

说明：如果当前节点为空，返回0；否则返回1（当前节点）加上左右子树的节点总数。

使用迭代方式（层序遍历）统计

也可以用队列实现广度优先遍历，逐个访问节点并计数。

造点AI

夸克 · 造点AI

325

查看详情

#include <queue>
int countNodesIterative(TreeNode* root) {
    if (root == nullptr) return 0;
<pre class='brush:php;toolbar:false;'>std::queue<TreeNode*> q;
q.push(root);
int count = 0;

while (!q.empty()) {
    TreeNode* node = q.front();
    q.pop();
    count++;

    if (node->left)  q.push(node->left);
    if (node->right) q.push(node->right);
}
return count;

登录后复制

}

说明：利用队列保存待访问的节点，每次出队一个节点就计数加1，并将其子节点入队。