ให้ต้นไม้ไบนารี ภารกิจคือตรวจสอบว่าเป็นต้นไม้ไบนารีแบบเต็มหรือไม่ Binary Tree จะเรียกว่า Full Binary Tree หากทุกโหนดมีลูกเป็นศูนย์หรือสองคน
ตัวอย่าง
อินพุต-1
ผลลัพธ์:
1
คำอธิบาย: ทุกโหนดยกเว้นโหนดปลายสุดมีลูกสองคน ดังนั้นจึงเป็นต้นไม้ไบนารีแบบเต็ม
อินพุต-2:
ผลลัพธ์:
0
คำอธิบาย: โหนด 2 มีลูกเพียงคนเดียว ดังนั้นจึงไม่ใช่ไบนารีทรีแบบเต็ม
แนวทางในการแก้ปัญหานี้
ในการตรวจสอบว่าไบนารีทรีที่กำหนดเต็มหรือไม่ เราสามารถตรวจซ้ำสำหรับทรีย่อยด้านซ้ายและทรีย่อยด้านขวาได้
- ป้อน Binary Tree ที่กำหนดซึ่งมีโหนดและโหนดย่อย
- ฟังก์ชันบูลีน isFullBinaryTree(Node*root) รับโหนดรูทเป็นอินพุตและคืนค่า True หากเป็นไบนารีทรีเต็ม มิฉะนั้นจะเป็นเท็จ
- ในเงื่อนไขพื้นฐาน หากรูทโหนดเป็น NULL หรือว่าง ให้คืนค่า True
- หากทรีย่อยด้านซ้ายและทรีย่อยด้านขวาเป็น NULL หรือว่างเปล่า ให้คืนค่า True
- ตอนนี้ ให้เราตรวจสอบแบบวนซ้ำสำหรับทรีย่อยด้านซ้ายและทรีย่อยด้านขวา แล้วส่งคืนผลลัพธ์
ตัวอย่าง
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
bool isFullBinaryTree(struct treenode * root) {
if (root == NULL) {
return true;
}
if (root -> left == NULL and root -> right == NULL) {
return true;
} else if (root -> left and root -> right) {
return (isFullBinaryTree(root -> left) and isFullBinaryTree(root -> right));
}
return false;
}
int main() {
struct treenode * root = NULL;
root = createNode(1);
root -> left = createNode(2);
root -> right = createNode(3);
root -> left -> right = createNode(4);
root -> left -> left = createNode(5);
root -> right -> left = createNode(6);
if (isFullBinaryTree(root)) {
cout << "1" << endl;
} else {
cout << "0" << endl;
}
return 0;
} การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น
ผลลัพธ์
0
คำอธิบาย: เนื่องจากโหนดปลายสุดทั้งหมดในไบนารีทรีที่กำหนดไม่มีโหนดลูก โหนดนี้จึงไม่ใช่ทรีไบนารีแบบเต็ม เราจะได้ผลลัพธ์เป็น 0
