统计二叉树的结点个数

好的，统计二叉树的节点个数同样可以使用递归的方法。对于一棵二叉树，它的节点个数等于根节点加上左子树的节点个数和右子树的节点个数之和。以下是统计二叉树节点个数的示例代码（假设二叉树已经存在，且每个节点包含一个整数值和左、右子节点指针）：

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

调用该函数并传入二叉树的根节点，即可得到二叉树的节点个数。

相关问题

统计二叉树结点个数c++

要统计二叉树的节点个数，可以使用递归的方式来实现。下面是一个使用C++实现的示例代码：

#include <iostream>

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

// 统计二叉树结点个数的函数
int countNodes(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    
    // 递归统计左子树和右子树的结点个数，加上根结点自身的个数
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    // 创建一个二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    // 统计结点个数并输出结果
    int nodeCount = countNodes(root);
    std::cout << "二叉树的结点个数为：" << nodeCount << std::endl;
    
    return 0;
}

上述代码定义了一个二叉树结点`TreeNode`，其中`val`表示结点的值，`left`和`right`分别指向左子树和右子树的指针。`countNodes`函数使用递归的方式统计二叉树的结点个数，如果根结点为空，则返回0；否则，返回左子树结点个数、右子树结点个数和根结点本身的个数之和。在`main`函数中创建了一个二叉树，并调用`countNodes`函数统计结点个数并输出结果。

统计二叉树结点个数pta

统计二叉树的节点个数通常涉及到对二叉树的遍历，特别是前序遍历、中序遍历或后序遍历。以下是几种常见的方法：

1. **递归法**：对于一棵二叉树，如果根节点存在，则它的节点个数等于左子树节点数加上右子树节点数加一（因为根节点本身也算一个）。这个过程可以用递归来实现。

2. **迭代法（栈）**：可以使用栈数据结构来进行非递归的前序遍历。从根节点开始，每访问一个节点就将其左右子节点依次入栈。当遍历到叶子节点时，说明已经统计完了所有节点，此时栈内元素个数就是节点总数减一。

3. **迭代法（Morris 遍历）**：这是一种空间效率较高的方法，利用线索二叉树的概念，通过修改原树结构达到“无额外存储空间”的效果，遍历过程中直接计算节点总数。

**Python 示例** (仅做概念演示，未包含边界条件检查)：

def count_nodes(root):
    if root is None:
        return 0

    # Morris遍历示例，这里假设root.left 和 root.right 指向空节点
    current = root
    count = 0
    while current:
        if not current.left:
            count += 1
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                count += 1
                current = current.right

    return count