二叉树中求非叶子节点的个数C++实现

在二叉树中，非叶子节点（即内部节点）是指那些至少有一个子节点的节点。为了计算非叶子节点的数量，我们可以在遍历二叉树的过程中计数。这里提供一种简单的递归方法：

#include <iostream>

// 定义二叉树节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int countNonLeafNodes(TreeNode* root) {
    // 如果根节点为空，返回0
    if (root == nullptr) return 0;

    // 一个节点如果是叶子节点，它要么没有左孩子，要么没有右孩子
    // 因此，如果同时存在左右孩子，则它是非叶子节点
    return (root->left && root->right) ? 1 + countNonLeafNodes(root->left) + countNonLeafNodes(root->right) : 0;
}

int main() {
    // 创建一个示例二叉树
    TreeNode* tree = new TreeNode(1);
    tree->left = new TreeNode(2);
    tree->right = new TreeNode(3);
    tree->left->left = new TreeNode(4);
    tree->left->right = new TreeNode(5);

    std::cout << "非叶子节点的数量: " << countNonLeafNodes(tree) << std::endl;

    delete tree;  // 别忘了释放内存
    return 0;
}

在这个C++程序中，`countNonLeafNodes` 函数接受一个二叉树的根节点作为输入，并通过递归遍历所有子节点来计算非叶子节点的数量。