我们得到一个具有“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: 8 Minimum no. of iterations to pass information to all nodes in the tree are: 8