数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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()和静态int check(const void *a_1, const void *b_1)。
调用外部参数化构造函数Tree::Tree(int nodes)
将this->nodes设置为nodes。
将List_children设置为new list[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()
将*ptr设置为new int[arr[vertices]]
将temp设置为0，temp_2设置为0
声明一个迭代器list::iterator it
从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)进行快速排序
从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为0开始循环，直到i < nodes并i++。在循环内，将ptr[i]设置为0
调用Iteration(0, ptr)并将temp设置为ptr[0]，并删除[] ptr
返回temp
调用类方法int Tree::check(const void * a_1, const void * b_1)
声明一个变量int result为(*(int*)b_1 - *(int*)a_1)
返回result
在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
658 次浏览
