数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 编写程序计算树的大小 - 递归
在这个问题中，我们给定一棵树，我们的任务是创建一个程序，使用递归来计算树的大小。
树的大小是树中存在的节点总数。
让我们举个例子来理解这个问题，
上面这棵树的大小是 5。
为了找到树的大小，我们将不得不加上左子树和右子树的大小，然后加 1。递归函数将被调用到树的左右两个子树。如果没有找到子树，则返回 0。
上面例子使用此方法解决
为了找到树的大小，
size(3) = size(5) + size(7) + 1
size(3) = (size(1) + size(9) + 1) + 1 + 1
size(3) = (1 + 1 + 1) + 1 + 1
size(3) = 5
程序说明我们解决方案的工作原理，
示例
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int findSize(node* node) {
if (node == NULL)
return 0;
else
return(findSize(node->left) + 1 + findSize(node->right));
}
int main() {
node *root = insertNode(6);
root->left = insertNode(3);
root->right = insertNode(7);
root->left->left = insertNode(1);
root->left->right = insertNode(5);
root->right->left = insertNode(2);
cout<<"The size of the given tree is "<<findSize(root);
return 0;
}输出
The size of the given tree is 6
更新于: 2020-04-20
2K+ 次查看
广告