C++에서 이진 트리의 모든 내부 노드 인쇄

이 문제에서는 이진 트리가 주어지고 이진 트리의 모든 내부 노드를 인쇄해야 합니다.

이진 트리 노드가 최대 2개의 자식 노드를 가질 수 있는 트리입니다. 노드 또는 정점에는 노드가 없을 수 있습니다. 하나의 자식 또는 두 개의 자식 노드가 있을 수 있습니다.

예시 -

내부 노드 하나 이상의 자식을 가질 수 있는 노드입니다. 즉, 잎이 아닌 노드는 내부 노드입니다.

문제를 이해하기 위해 예를 들어 보겠습니다 -

출력 − 7 4 9

이 문제를 해결하기 위해 BFS(breadth-first search) 순회를 사용하여 이진 트리를 순회합니다.

순회하는 동안 노드를 대기열로 푸시합니다. 큐에서 요소를 팝하면 자식 노드가 없는 트리의 모든 노드를 인쇄합니다.

예시

우리의 논리는 아래 코드로 구현됩니다 -

#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