ในปัญหานี้ เราได้รับต้นไม้และงานของเราคือการสร้างโปรแกรมเพื่อคำนวณขนาดของต้นไม้โดยใช้การเรียกซ้ำ
ขนาดของต้นไม้คือจำนวนโหนดทั้งหมดที่มีอยู่ในต้นไม้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ขนาดของต้นด้านบนคือ 5.
ในการหาขนาดของต้นไม้ เราจะต้องเพิ่มขนาดของทรีย่อยด้านซ้ายและแผนผังย่อยด้านขวา จากนั้นเพิ่มขึ้น 1 ฟังก์ชันแบบเรียกซ้ำจะถูกเรียกสำหรับทั้งทรีย่อยด้านซ้ายและขวาของทรี และหากไม่พบแผนผังย่อยให้คืนค่า 0
ตัวอย่างข้างต้นแก้ไขโดยใช้วิธีนี้
การหาขนาดของต้นไม้
ขนาด(3) =ขนาด(5) + ขนาด(7) + 1
ขนาด(3) =(ขนาด(1) + ขนาด(9) + 1) + 1 + 1
ขนาด(3) =(1 + 1 + 1) + 1 + 1
ขนาด(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
