首页 > 后端开发 > C++ > 正文

给定一个非循环图,计算每个深度的最小元素之和

PHPz
发布: 2023-09-10 18:49:01
转载
940 人浏览过

不包含任何循环或回路的图被称为非循环图。树是一种非循环图,其中每个节点都与另一个唯一节点相连。非循环图也被称为无环图。

循环图与非循环图的区别 -

的中文翻译为:

Cycle Graph

循环图

非循环图

图形形成一个闭环。

图表没有形成闭环。

图表中不包含深度循环

图表包含每个深度。

示例 1

让我们举一个循环图的例子 −

当闭环存在时,就形成了循环图。

给定一个非循环图,计算每个深度的最小元素之和

Figure I代表了循环图,不包含深度节点。

Example 2

的翻译为:

示例2

让我们以一个非循环图的例子来说明:

给定一个非循环图,计算每个深度的最小元素之和

树的根节点称为零深度节点。在图 II 中,在零深度处只有一个根,即 2。因此它被认为是最小深度为零的节点。

在第一个深度节点中,我们有3个节点元素,如4、9和1,但最小的元素是4

在第二个深度节点中,我们再次有3个节点元素,如6、3和1,但最小元素是1

我们将知道总深度节点是如何得出的,

总深度节点 = Zero_Depth 节点的最小值 + First_Depth 节点的最小值 + Zero_Depth 节点的最小值

总深度节点 = 2 + 4 + 3 = 9。所以,9是非循环图的总最小和。

语法

The following syntax used in the program:
struct name_of_structure{
   data_type var_name;   
   // data member or field of the structure.
}
登录后复制
  • struct − 该关键字用于表示结构数据类型。

  • name_of_struct - 我们为结构提供任何名称。

  • 结构是将各种相关变量集中在一个地方的集合。

Queue < pair < datatype, datatype> > queue_of_pair
登录后复制
make_pair() 
登录后复制

参数

C++ 中的对队列 -

  • 这是用于组合两种不同数据类型的队列对的通用 STL 模板,队列对位于实用程序头文件下。

  • Queue_of_pair - 我们为该对指定任何名称。

  • make_pair() - 用于构造具有两个元素的pair对象。

name_of_queue.push()
登录后复制

参数

  • name_of_queue - 我们正在命名队列名称。

  • push() − 这是一个预定义的方法,属于队列头部的一部分,push方法的作用是插入元素或值。

name_of_queue.pop()
登录后复制

参数

  • name_of_queue − 我们正在给队列命名。

  • pop() − 这是一个预定义的方法,属于队列头文件,并且使用pop方法是为了删除整个元素或值。

算法

  • 我们将启动程序头文件,即'iostream'、'climits'、'utility'、'queue'。

    < /里>
  • 我们正在创建具有整数值“val”的结构“tree_node”来获取节点值。然后我们用给定的数据创建tree_node指针来初始化左子节点和右子节点来存储值。接下来,我们创建一个 tree_node 函数,其中 int x 作为参数传递,并验证它是否等于 'val' 整数,并将左右子节点分配为 null 。

  • 现在我们将定义一个函数 minimum_sum_at_each_depth(),它接受一个整数值作为参数,用于找到每个深度的最小和。使用 if- 语句,它检查树的根值是否为空,如果为空则返回 0。

  • 我们正在创建STL(标准模板库)的队列对,以组合两个值。

  • 我们创建了一个名为q的队列变量,它作为一对进行两个方法,即push()make_pair()。使用这两个方法,我们插入值并构造了一个对象的两对。

  • 我们正在初始化三个变量,即 'present_depth','present_sum' 和 'totalSum',这些变量将用于进一步找到当前总和以及找到总最小总和。

  • 在初始化变量之后,我们创建一个while循环来检查条件,如果队列对不为空,则节点的计数将从开头开始。接下来,我们使用‘pop()’方法删除一个现有的节点,因为它将移动到树的下一个深度来计算最小和。

  • 现在我们将创建三个 if 语句来返回总和的最小和。

  • 在此之后,我们将开始主要的函数,并借助根指针、左右子节点分别构建输入模式的树形结构,并通过新的‘tree_node’传递节点值。

  • 最后,我们调用‘minimum_sum_at_each_depth(root)’函数并传递参数root来计算每个深度的最小总和。接下来,打印语句“非循环图各深度的总和”并得到结果。

请记住,对队列是一个包含队列元素对的容器。

Example

的中文翻译为:

示例

在这个程序中,我们将计算每个深度的所有最小节点的总和。

给定一个非循环图,计算每个深度的最小元素之和

在图二中,总深度的最小和为15+8+4+1 = 13。

现在我们将把这个数字作为该程序的输入。

#include <iostream>
#include <queue> 

// required for FIFO operation
#include <utility> 

// required for queue pair
#include <climits>
using namespace std;

// create the structure definition for a binary tree node of non-cycle graph
struct tree_node {
   int val;
   tree_node *left;
   tree_node *right;
   tree_node(int x) {
      val = x;
      left = NULL;
      right = NULL;
   }
};
// This function is used to find the minimum sum at each depth
int minimum_sum_at_each_depth(tree_node* root) {
   if (root == NULL) {
      return 0;
   }
   queue<pair<tree_node*, int>> q;
   // create a queue to store node and depth and include pair to combine two together values.
   q.push(make_pair(root, 0)); 
   
   // construct a pair object with two element
   int present_depth = -1; 
   
   // present depth
   int present_sum = 0; 
   
   // present sum for present depth
   int totalSum = 0; 
   
   // Total sum for all depths
   while (!q.empty()) {
      pair<tree_node*, int> present = q.front(); 
      
      // assign queue pair - present
      q.pop();
      
      // delete an existing element from the beginning
      if (present.second != present_depth) {
      
         // We are moving to a new depth, so update the total sum and reset the present sum
         present_depth = present.second;
         totalSum += present_sum;
         present_sum = INT_MAX;
      }

      // Update the present sum with the value of the present node
      present_sum = min(present_sum, present.first->val);
      
      //We are adding left and right children to the queue for updating the new depth.
      if (present.first->left) {
         q.push(make_pair(present.first->left, present.second + 1));
      }
      if (present.first->right) {
         q.push(make_pair(present.first->right, present.second + 1));
      }
   }
   
   // We are adding the present sum of last depth to the total sum
   totalSum += present_sum;
   return totalSum;
}

// start the main function
int main() {
   tree_node *root = new tree_node(15);
   root->left = new tree_node(14);
   root->left->left = new tree_node(11);
   root->left->right = new tree_node(4);
   root->right = new tree_node(8);
   root->right->left = new tree_node(13);
   root->right->right = new tree_node(16);
   root->left->left->left = new tree_node(1);
   root->left->right->left = new tree_node(6);
   root->right->right->right = new tree_node(2);
   root->right->left->right = new tree_node(7);

   cout << "Total sum at each depth of non cycle graph: " << minimum_sum_at_each_depth(root) << endl; 
   return 0;
}
登录后复制

输出

Total sum at each depth of non cycle graph: 28
登录后复制

结论

我们探讨了给定非循环图中每个深度的元素最小和的概念。我们看到箭头运算符连接节点并构建树形结构,利用它计算每个深度的最小和。该应用程序使用非循环图,例如城市规划、网络拓扑、谷歌地图等。

以上是给定一个非循环图,计算每个深度的最小元素之和的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!