Trong bài toán này, chúng ta được cung cấp một cây nhị phân và chúng ta phải in tất cả các nút bên trong của cây nhị phân.
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ụ -
Nút nội bộ là nút có thể có ít nhất một nút con, tức là nút không phải là nút bên trong.
Hãy lấy một ví dụ để hiểu vấn đề -
Đầu ra - 7 4 9
Để giải quyết vấn đề này, chúng tôi sẽ duyệt qua cây nhị phân bằng cách sử dụng BFS (tìm kiếm theo chiều rộng-đầu tiên).
Trong khi duyệt, chúng tôi sẽ đẩy các nút vào một hàng đợi. Khi chúng tôi bật các phần tử từ hàng đợi, chúng tôi sẽ in tất cả các nút của cây không có bất kỳ nút con nào.
Ví dụ
Logic của chúng tôi được thực hiện bởi đoạn mã dưới đây -
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int data){
left = right = NULL;
this->data = data;
}
};
void printNonLeafNodes(Node* root) {
queue<Node*> treeNodes;
treeNodes.push(root);
while (!treeNodes.empty()) {
Node* curr = treeNodes.front();
treeNodes.pop();
bool isInternal = 0;
if (curr->left) {
isInternal = 1;
treeNodes.push(curr->left);
}
if (curr->right) {
isInternal = 1;
treeNodes.push(curr->right);
}
if (isInternal)
cout<<curr->data<<"\t";
}
}
int main() {
Node* root = new Node(43);
root->left = new Node(12);
root->right = new Node(78);
root->left->left = new Node(4);
root->right->left = new Node(9);
root->right->right = new Node(1);
root->right->right->right = new Node(50);
root->right->right->left = new Node(25);
cout<<"All internal Nodes of the binary tree are :\n";
printNonLeafNodes(root);
return 0;
} Đầu ra
All internal Nodes of the binary tree are − 43 12 78 1