Với một Cây nhị phân, nhiệm vụ là kiểm tra xem nó có phải là Cây nhị phân đầy đủ hay không. Cây nhị phân được cho là Cây nhị phân đầy đủ nếu mọi nút đều có 0 hoặc hai nút con.
Ví dụ
Đầu vào-1
Đầu ra:
1
Giải thích: Mọi nút ngoại trừ nút lá đều có hai nút con, vì vậy nó là một cây nhị phân đầy đủ.
Đầu vào-2:
Đầu ra:
0
Giải thích: Nút 2 chỉ có một nút con, vì vậy nó không phải là một cây nhị phân đầy đủ.
Phương pháp tiếp cận để giải quyết vấn đề này
Để kiểm tra xem một cây nhị phân đã cho đã đầy hay chưa, chúng ta có thể kiểm tra đệ quy đối với cây con bên trái và cây con bên phải.
- Nhập một Cây nhị phân nhất định có các nút và các nút con của nó.
- Một hàm Boolean isFullBinaryTree (Node * root) lấy nút gốc làm đầu vào và trả về True nếu nó là cây nhị phân đầy đủ, ngược lại là false.
- Trong điều kiện cơ sở, nếu nút gốc là NULL hoặc rỗng, thì trả về True.
- Nếu cây con bên trái và cây con bên phải là NULL hoặc trống, thì trả về True.
- Bây giờ, chúng ta hãy kiểm tra đệ quy từng cây con bên trái và cây con bên phải và trả về kết quả đầu ra.
Ví dụ
#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;
} Chạy đoạn mã trên sẽ tạo ra kết quả là,
Đầu ra
0
Giải thích: Vì tất cả các nút lá trong cây nhị phân đã cho không có nút con nên nó không phải là Cây nhị phân đầy đủ. Vì vậy, chúng tôi nhận được đầu ra là 0.