Trong bài toán này, chúng ta được đưa ra một cây và nhiệm vụ của chúng ta là tạo một chương trình để tính toán kích thước của cây bằng cách sử dụng đệ quy.
Kích thước của cây là tổng số nút có trong cây.
Hãy lấy một ví dụ để hiểu vấn đề,
Kích thước của cây trên là 5.
Để tìm kích thước của cây, chúng ta sẽ phải cộng kích thước của cây con bên trái và cây con bên phải rồi tăng nó lên 1. Hàm đệ quy sẽ được gọi cho cả cây con bên trái và bên phải của cây. Và nếu không tìm thấy cây con nào, trả về 0.
Ví dụ trên được giải quyết bằng phương pháp này
Để tìm kích thước của cây,
size (3) =size (5) + size (7) + 1
size (3) =(size (1) + size (9) + 1) + 1 + 1
kích thước (3) =(1 + 1 + 1) + 1 + 1
kích thước (3) =5
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The size of the given tree is 6