最小数C++のツリー内のすべてのノードに情報を渡すための反復回数

「n」個のノードを持つツリーデータ構造が与えられます。指定されたツリーにはルートノードとそれぞれの子があり、それぞれの子は任意の数であり、さらに子は任意の数の子を持つことができます。タスクは、ツリーのルートノードがツリー内のすべてのノードに情報を渡すために必要な最小反復回数を見つけることです。一度に、ノードはその子の1つに情報を渡すことができ、さらにその子の1つはその子の1つに情報を渡すことができ、その間、ルートノードは別の子に情報を渡すことができます。

このためのさまざまな入出力シナリオを見てみましょう-

で-

アウト- 最小数ツリー内のすべてのノードに情報を渡すための反復回数は次のとおりです。5

説明- ルートと他のすべてのノードを含む合計11個のノードを持つツリーが与えられます。特定のツリーのルートノードは0です。これは、多くの子があり、次に他のノードがあるため、最初にノード1にデータを渡します。次に、ルートノードはノード4にデータを渡し、次に3にデータを渡し、次に渡します。データを6に、最後にデータを2に渡します。したがって、必要な反復は合計で5です。

で-

アウト- 最小数ツリー内のすべてのノードに情報を渡すための反復回数は次のとおりです。1

説明- ：ルートと他のすべてのノードを含む合計2つのノードを持つツリーが与えられます。特定のツリーにはルートノードの子が1つしかないため、必要な反復の最小数は1になります。

以下のプログラムで使用されるアプローチは次のとおりです-

• ツリーを構築するクラスを作成し、そのデータメンバーとしてノードを追加し、List_childrenとしてリストポインターを作成し、void Iteration（int vertices、int arr []）としてプライベートメソッドを宣言します。パラメータ化されたコンストラクタをTree（intノード）、void insert_node（int a、int b）、int Min_Iteration（）、およびstatic int check（const void * a_1、const void * b_1）として宣言します。

• 外部のパラメーター化されたコンストラクターをTree::Tree（intノード）

  として呼び出します。

  • this->nodesをnodesに設定します。

  • List_childrenを新しいlist[nodes]

    に設定します

• クラスメソッドをvoidTree::insert_node（int a、int b）

  として呼び出します。

  • List_children [a]をpush_back（b）に設定します

• クラスメソッドをvoidTree::Iteration（int vertices、int arr []）

  として呼び出します。

  • arr[vertices]をList_children[vertices].size（）

    に設定します

  • *ptrをnewint[arr [vertices]]

    に設定します

  • tempを0に、temp_2を0に設定します

  • イテレータをlist::iterator it

    として宣言します

  • それからList_children[vertices].begin（）へのループFORを開始し、List_children [vertices] .end（）と等しくならないようにして、事前にインクリメントします。ループ内でIteration（* it、arr）を設定し、ptr[temp++]をarr[*it]

    に設定します。

  • クイックソートを行うには、qsort（ptr、arr [vertices]、sizeof（int）、check）を呼び出します

  • ループFORtempを0に開始し、tempをList_children [vertices] .size（）未満にして、増分tempをポストします。ループ内で、temp_2をptr [temp] + temp + 1に設定し、arr [vertices]をmax（arr [vertices]、temp_2）に設定し、delete [] ptr

• クラスメソッドをintTree::Min_Iteration（）

  として呼び出します。

  • ポインタをint*ptr =new int [nodes]

    として宣言します

  • 変数をinttemp=-1

    として宣言します

  • i<ノードおよびi++まで、ループFORをiから0まで開始します。ループ内で、ptr[i]を0に設定します

  • Iteration（0、ptr）を呼び出し、tempをptr[0]に設定してdelete[] ptr

  • 温度を返す

• クラスメソッドをintTree::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