ในปัญหานี้ เราได้รับไบนารีทรีและเราต้องพิมพ์โหนดภายในทั้งหมดของแผนผังไบนารี
ต้นไม้ไบนารี เป็นต้นไม้ที่โหนดสามารถมีโหนดย่อยได้สูงสุด 2 โหนด โหนดหรือจุดยอดต้องไม่มีโหนด โหนดย่อยหนึ่งโหนดหรือโหนดย่อยสองโหนด
ตัวอย่าง −
โหนดภายใน เป็นโหนดที่สามารถมีลูกได้อย่างน้อยหนึ่งโหนด เช่น โหนดที่ไม่ใช่โหนดลีฟคือโหนดภายใน
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
ผลผลิต − 7 4 9
เพื่อแก้ปัญหานี้ เราจะสำรวจไบนารีทรีโดยใช้การข้ามผ่าน BFS (การค้นหาแบบกว้างก่อน)
ระหว่างการเดินทาง เราจะพุชโหนดไปยังคิว เมื่อเราเปิดองค์ประกอบจากคิว เราจะพิมพ์โหนดทั้งหมดของทรีที่ไม่มีโหนดย่อย
ตัวอย่าง
ตรรกะของเราใช้งานโดยโค้ดด้านล่าง -
#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;
} ผลลัพธ์
All internal Nodes of the binary tree are − 43 12 78 1
