请帮我写个C++的递归算法,计算一棵二叉树的节点
时间: 2024-05-10 12:20:45 浏览: 5
以下是计算二叉树节点的递归算法:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int countNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
```
这个算法定义了一个名为 `countNodes` 的函数,它接受一个指向根节点的指针,返回这棵二叉树的节点数。当根节点为空时,返回 0。否则,返回左子树节点数加右子树节点数再加上 1(因为根节点也算一个节点)。这里使用了递归,通过不断地调用自身来计算节点数。
相关问题
帮我写一段二叉树算法C++代码
好的,下面是一个简单的二叉树遍历算法的C++代码:
```c++
#include <iostream>
using namespace std;
// 二叉树节点结构
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int data) {
this->data = data;
left = nullptr;
right = nullptr;
}
};
// 二叉树遍历函数
void traverse(TreeNode* node) {
if (node == nullptr) {
return;
}
traverse(node->left);
traverse(node->right);
cout << node->data << " ";
}
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);
// 遍历二叉树
cout << "二叉树遍历结果: ";
traverse(root);
return 0;
}
```
这个程序创建了一个二叉树,并使用递归函数`traverse()`遍历二叉树。这里使用的是后序遍历算法,即先遍历左子树,再遍历右子树,最后访问根节点。
用c++语言写二叉树中序遍历的递归算法
二叉树的中序遍历是指先遍历左子树,再遍历根节点,最后遍历右子树。
递归算法的核心思想是先递归遍历左子树,然后输出根节点,最后递归遍历右子树。
下面是用 C++ 语言写二叉树中序遍历的递归算法的代码:
```cpp
#include <iostream>
using namespace std;
// 二叉树结点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 中序遍历的递归算法
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left); // 递归遍历左子树
cout << root->val << " "; // 输出根节点
inorderTraversal(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);
// 中序遍历二叉树
inorderTraversal(root);
cout << endl;
return 0;
}
```
输出结果为:
```
4 2 5 1 3
```
说明递归算法实现了二叉树的中序遍历。