최소 번호 C++에서 트리의 모든 노드에 정보를 전달하기 위한 반복

n개의 노드가 있는 트리 데이터 구조가 제공됩니다. 주어진 트리에는 루트 노드와 각각의 자식이 있으며, 이 자식은 임의의 수일 수 있으며 추가 자식은 임의의 수의 자식을 가질 수 있습니다. 작업은 트리의 모든 노드에 정보를 전달하기 위해 트리의 루트 노드에 필요한 최소 반복 횟수를 찾는 것입니다. 한 번에 노드는 자식 중 하나에 정보를 전달할 수 있고 다른 자식 중 하나는 정보를 자식 중 하나로 전달할 수 있으며 루트 노드는 다른 자식에게 정보를 전달할 수 있습니다.

이에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다. -

안에 -

아웃 - 최소 번호 트리의 모든 노드에 정보를 전달하는 반복 횟수는 다음과 같습니다. 5

설명 - 루트와 다른 모든 노드를 포함하여 총 11개의 노드가 있는 트리가 제공됩니다. 주어진 트리의 루트 노드는 0이며 많은 자식이 있고 다른 노드가 있으므로 먼저 노드 1에 데이터를 전달하고 루트 노드는 노드 4에 데이터를 전달한 다음 3에 데이터를 전달한 다음 전달합니다. 데이터를 6으로 전달하고 마침내 데이터를 2로 전달합니다. 따라서 필요한 반복은 총 5회입니다.

안에 -

아웃 - 최소 번호 트리의 모든 노드에 정보를 전달하는 반복 횟수는 다음과 같습니다. 1

설명 - :루트와 다른 모든 노드를 포함하여 총 2개의 노드가 있는 트리가 주어집니다. 주어진 트리에 루트 노드의 자식이 하나만 있으므로 필요한 최소 반복 횟수는 1입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -

• 트리를 구성하는 클래스를 만들고 데이터 멤버로 노드를 추가하고 List_children으로 목록 포인터를 만들고 개인 메서드를 void Iteration(int vertices, int arr[])으로 선언합니다. 매개변수화된 생성자를 Tree(int nodes), void insert_node(int a, int b), int Min_Iteration() 및 static int check(const void *a_1, const void *b_1)로 선언합니다.

• 외부 매개변수화된 생성자를 Tree::Tree(int nodes)

  로 호출합니다.

  • 이->노드를 노드로 설정합니다.

  • List_children을 새 목록[노드]로 설정

• void Tree::insert_node(int a, int b)

  로 클래스 메서드를 호출합니다.

  • List_children[a]을 push_back(b)

    으로 설정

• void Tree::Iteration(int vertices, int arr[])

  으로 클래스 메서드를 호출합니다.

  • arr[vertices]를 List_children[vertices].size()

    로 설정합니다.

  • *ptr을 새로운 int[arr[vertices]]

    로 설정

  • temp를 0으로 설정하고 temp_2를 0으로 설정

  • iterator를 list::iterator it

    으로 선언하십시오.

  • 그것이 List_children[vertices].end()와 같지 않을 때까지 그것에서 List_children[vertices].begin()까지 FOR 루프를 시작하고 그것을 사전 증가시킵니다. 루프 내에서 Iteration(*it, arr)을 설정하고 ptr[temp++]을 arr[*it]

    로 설정합니다.

  • 빠른 정렬을 위해 qsort(ptr, arr[vertices], sizeof(int), check) 호출

  • 루프 FOR temp를 0으로 시작하고 temp는 List_children[vertices].size()보다 낮고 temp를 증가시킵니다. 루프 내에서 temp_2를 ptr[temp] + temp + 1로 설정하고 arr[vertices]를 max(arr[vertices], temp_2)로 설정하고 [] ptr

    를 삭제합니다.

• 클래스 메서드를 int Tree::Min_Iteration()

  으로 호출합니다.

  • 포인터를 int *ptr =new int[nodes]

    로 선언합니다.

  • 변수를 int temp =-1

    로 선언합니다.

  • i <노드 및 i++까지 루프 FOR를 i에서 0으로 시작합니다. 루프 내에서 ptr[i]를 0으로 설정

  • Iteration(0, ptr)을 호출하고 temp를 ptr[0]으로 설정하고 [] ptr

    을 삭제합니다.

  • 반환 온도

• 클래스 메서드를 int Tree::check(const void * a_1, const void * b_1)

  로 호출합니다.

  • 변수를 int 결과로 선언하여 ( *(int*)b_1 - *(int*)a_1 )

  • 반환 결과

• main() 함수에서

  • 매개변수화된 생성자를 사용하여 트리 개체를 만듭니다.

  • 그런 다음 트리 클래스의 개체를 사용하여 insert_node() 메서드를 호출하여 노드 데이터를 트리에 삽입합니다.

  • Min_Iteration() 메서드를 호출하여 트리의 모든 노드에 정보를 전달하기 위한 최소 반복 횟수를 계산합니다.

예시

#include<bits/stdc++.h>
using namespace std;

class Tree
{
   int nodes;
   list<int> *List_children;
   void Iteration(int vertices, int arr[]);

public:
   //constructor of a class
   Tree(int nodes);
   //method to insert a node in a tree
   void insert_node(int a, int b);
   //method to calculate the minimum iterations
   int Min_Iteration();
   static int check(const void *a_1, const void *b_1);
};

Tree::Tree(int nodes)
{
   this->nodes = nodes;
   List_children = new list<int>[nodes];
}
void Tree::insert_node(int a, int b)
{
   List_children[a].push_back(b);
}
void Tree::Iteration(int vertices, int arr[])
{
   arr[vertices] = List_children[vertices].size();
   int *ptr = new int[arr[vertices]];
   int temp = 0;
   int temp_2 = 0;
   list<int>::iterator it;

   for(it = List_children[vertices].begin(); it!= List_children[vertices].end(); ++it)
   {
      Iteration(*it, arr);
      ptr[temp++] = arr[*it];
   }

   qsort(ptr, arr[vertices], sizeof(int), check);

   for(temp = 0; temp < List_children[vertices].size(); temp++)
   {
      temp_2 = ptr[temp] + temp + 1;
      arr[vertices] = max(arr[vertices], temp_2);
   }
   delete[] ptr;
}
int Tree::Min_Iteration()
{
   int *ptr = new int[nodes];
   int temp = -1;

   for (int i = 0; i < nodes; i++)
   {
      ptr[i] = 0;
   }
   Iteration(0, ptr);
   temp = ptr[0];
   delete[] ptr;
   return temp;
}
int Tree::check(const void * a_1, const void * b_1)
{
}
int main()
{
   Tree T_1(8);
   T_1.insert_node(0, 1);
   T_1.insert_node(0, 3);
   T_1.insert_node(0, 4);
   T_1.insert_node(0, 6);
   T_1.insert_node(0, 2);
   T_1.insert_node(1, 7);
   T_1.insert_node(1, 2);
   T_1.insert_node(1, 3);
   T_1.insert_node(4, 6);
   T_1.insert_node(4, 7);
   cout<<"Minimum no. of iterations to pass information to all nodes in the tree are:"<<T_1.Min_Iteration();

   Tree T_2(2);
   T_2.insert_node(0, 1);
   cout<<"\nMinimum no. of iterations to pass information to all nodes in the tree are:" <<T_1.Min_Iteration();

   return 0;
}

출력

위 코드를 실행하면 다음 출력이 생성됩니다.

Minimum no. of iterations to pass information to all nodes in the tree are: 8
Minimum no. of iterations to pass information to all nodes in the tree are: 8