Computer >> 컴퓨터 >  >> 프로그램 작성 >> C 프로그래밍

C 프로그램에서 이진 트리의 맨 왼쪽 및 맨 오른쪽 노드를 인쇄합니다.

<시간/>

왼쪽 및 오른쪽 자식이 있는 이진 트리가 주어지고 주어진 트리의 정확한 오른쪽 및 왼쪽 자식을 인쇄하는 것이 작업입니다.

가장 왼쪽에 있는 노드는 트리의 부모 노드에서 왼쪽에 연결된 노드이고 가장 오른쪽에 있는 노드는 루트의 부모 노드에서 오른쪽에 연결된 노드입니다.

예시

Input: 106 20 320 100 21 61 52
Output: 106 20 320 100 52

C 프로그램에서 이진 트리의 맨 왼쪽 및 맨 오른쪽 노드를 인쇄합니다.

알고리즘

Start
Step 1 -> create structure of a node
   Declare int data
   Declare struct node *left and *right
Step 2 -> create struct node* newNode(int val)
   Create node* temp=new node
   Set temp->data = val
   Set temp->left = temp->right = NULL
   return (temp)
step 3 -> Declare Function void print(node *root)
   IF root == NULL
      Return
   Use STL queue<node*> que
   Call que.push(root)
   Use STL vector<int> ans
   Loop While !que.empty()
   Set int n = que.size()
   Loop for int i =0 and i<n and i++
      Set node *temp = que.front()
      Set que.pop()
      IF i=0
         Set ans.push_back(temp->data)
      End
      Else IF i=n-1
         Set ans.push_back(temp->data)
      End
      If temp->left
         Set que.push(temp->left)
      End
      IF temp->right
         Set que.push(temp->right)
      End
   End
   Loop For auto i : ans
      Print i
   End
Step 4 -> In main()
   Declare node *root = newNode(106) to create a node
   Call print(root)
stop

예시

#include <bits/stdc++.h>
using namespace std;
//structure of a node {
   int data;
   struct node* left, *right;
};
//structure to create a new node
struct node* newNode(int val){
   node* temp = new node;
   temp->data = val;
   temp->left = temp->right = NULL;
   return (temp);
}
//function to print corner elements of a tree
void print(node *root) {
   if(root == NULL)
   return;
   queue<node*> que;
   que.push(root);
   vector<int> ans;
   while(!que.empty()){
      int n = que.size();
      for(int i =0;i<n;i++){
         node *temp = que.front();
         que.pop();
         if(i==0)
            ans.push_back(temp->data);
         else if(i==n-1)
            ans.push_back(temp->data);
         if(temp->left)
            que.push(temp->left);
         if(temp->right)
            que.push(temp->right);
      }
   }
   for(auto i : ans)
      cout << i << " ";
}
int main (){
   node *root = newNode(106);
   root->left = newNode(20);
   root->right = newNode(320);
   root->left->left = newNode(100);
   root->left->right = newNode(21);
   root->right->left = newNode(61);
   root->right->right = newNode(52);
   print(root);
   return 0;
}

출력

위의 프로그램을 실행하면 다음 출력이 생성됩니다.

106 20 320 100 52