最低数量 在 C++ 中将信息传递给树中所有节点的迭代次数
我们得到一个具有“n”个节点的树数据结构。给定的树将有一个根节点和可以是任意数量的相应子节点，并且进一步的子节点可以有任意数量的子节点。任务是找到树的根节点所需的最小迭代次数，以将信息传递给树中的所有节点。一次，一个节点可以将信息传递给它的一个孩子，并且它的另一个孩子可以将信息传递给它的一个孩子，同时根节点可以将信息传递给另一个孩子。
让我们看看各种输入输出场景 -
在 -
Out -最小数量。将信息传递给树中所有节点的迭代次数为：5
解释 -我们得到一棵树，共有 11 个节点，包括根节点和所有其他节点。给定树的根节点为 0，它将首先将数据传递给节点 1，因为它有很多子节点，然后是其他节点，然后根节点将数据传递给节点 4，然后将数据传递给节点 3，然后它会传递数据到 6，最后它将数据传递到 2。因此，总共需要 5 次迭代。
在 -
Out -最小数量。将信息传递给树中所有节点的迭代次数为：1
解释 -：我们得到一棵树，总共有 2 个节点，包括根节点和所有其他节点。由于给定树中的根节点只有一个子节点，因此所需的最小迭代次数为 1。
以下程序中使用的方法如下 -
创建一个类来构造树并添加节点作为其数据成员，并创建一个列表指针作为 List_children 并将私有方法声明为 void Iteration(int vertices, int arr[])。将参数化构造函数声明为Tree(int nodes)、 void insert_node(int a, int b)、 intMin_Iteration()和 static int check(const void *a_1, const void *b_1)。
将外部参数化构造函数调用为 Tree::Tree(int nodes)
将 this->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
将迭代器声明为 list::iterator it
从它开始循环 FOR 到 List_children[vertices]。begin()直到它不等于 List_children[vertices]。end()并预先增加它。在循环内部设置 Iteration(*it, arr) 并将 ptr[temp++] 设置为 arr[*it]
调用 qsort(ptr, arr[vertices], sizeof(int), check) 进行快速排序
开始循环 FOR temp 到 0 并且 temp 小于 List_children[vertices]。size()并发布增量温度。在循环内部，将 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
从 i 开始循环 FOR 到 0 直到 i < 节点和 i++。在循环内部，将 ptr[i] 设置为 0
调用 Iteration(0, ptr) 并将 temp 设置为 ptr[0] 和 delete[] 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:
//类的构造函数
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)
{
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: 8Minimum no. of iterations to pass information to all nodes in the tree are: 8
以上是 最低数量 在 C++ 中将信息传递给树中所有节点的迭代次数 的全部内容， 来源链接： utcz.com/z/363261.html
