Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng ta là in tất cả các nút của cây là các nút đầy đủ.
Cây nhị phân là cây trong đó một nút có thể có tối đa 2 nút con. Nút hoặc đỉnh có thể không có nút, một nút con hoặc hai nút con.
Ví dụ -
Một nút đầy đủ là một nút có sẵn cả nút con bên trái và bên phải của nó. Nói cách khác, một nút có con bên trái và bên phải là một nút đầy đủ. Trong cây nhị phân ở trên, 4 và 9 là các nút đầy đủ.
Hãy lấy một ví dụ để hiểu vấn đề -
Đầu ra - 4 9
Một cách tiếp cận đơn giản và dễ dàng để giải quyết vấn đề này là duyệt cây bằng bất kỳ thuật toán duyệt nào. Kiểm tra xem nút hiện tại có nút con hoặc nút trái và phải hay không. Nếu có thì hãy in giá trị của nút, nếu không thì hãy để nguyên.
Ví dụ
Chương trình minh họa giải pháp của chúng tôi,
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node *left, *right;
};
Node *insertNode(int data){
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printFullNode(Node *root){
if (root != NULL){
printFullNode(root->left);
if (root->left != NULL && root->right != NULL)
cout<<root->data<<"\t";
printFullNode(root->right);
}
}
int main(){
Node* root = insertNode(100);
root->left = insertNode(56);
root->right = insertNode(12);
root->left->left = insertNode(89);
root->right->left = insertNode(32);
root->right->right = insertNode(45);
cout<<"All full nodes of the tree are :\n";
printFullNode(root);
return 0;
} Đầu ra
All full nodes of the tree are − 100 12