数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究从节点 X 出发，查找距离最多为 D 的子树中的最小权重
在进行计算机编程时，有时需要找到从特定节点开始的子树的最小权重，条件是子树不得包含任何距离指定节点超过 D 个单位的节点。这个问题出现在各个领域和应用中，包括图论、基于树的算法和网络优化。
子树构成更大树结构的一个子集，其中指定的节点充当子树的根。子树包含根节点的所有后代及其连接的边。节点的权重是指分配给该节点的特定值，可以表示其重要性、意义或任何其他相关指标。在本问题中，目标是在子树中的所有节点中找到最小权重，同时将子树限制在距离根节点最多 D 个单位的节点。
在下面的文章中，我们将深入探讨从节点 X 出发，距离不超过 D 的子树中查找最小权重的细节。
方法
方法 1 − 深度优先搜索 (DFS)，解决此问题最常见和最直接的方法之一是使用子树的深度优先搜索 (DFS) 遍历。
方法 2 − 解决此问题的另一种方法是使用子树的广度优先搜索 (BFS) 遍历。
语法
所示语法声明了一个名为 findMinimumWeight 的函数，该函数接受两个参数。第一个参数 Node* x 是指向二叉树中节点的指针，第二个参数 int d 是表示距离的整数。该函数返回一个整数 minWeight。在给定的代码片段中，没有指定查找从节点 x 出发，距离最多为 d 的节点的子树的最小权重的算法的实现。
int findMinimumWeight(Node* x, int d) {
// Implementation of the algorithm
// ...
return minWeight;
}
其中 −
Node* x 表示指向树的根节点的指针。
int d 表示子树中节点距根节点的最大距离的约束。
算法
计算机科学中一个复杂的挑战涉及确定一个子树的最小权重，该子树跨越从给定节点 X 出发，距离不超过 D 的节点。可以使用多种算法来解决此问题。在这里，我们介绍该方法的高级概述 −
步骤 1 − 以节点 X 作为子树的根开始。
步骤 2 − 以深度优先的方式遍历子树，仔细记录每个节点距根节点的距离。
步骤 3 − 维持一个变量来跟踪迄今为止遇到的最小权重。
步骤 4 − 在每个节点处，评估其距根节点的距离是否在 D 限制范围内。如果是，则使用当前节点的权重更新最小权重变量。
步骤 5 − 对子树中的所有节点重复步骤 3 和 4。
步骤 6 − 最终，返回从子树获得的最小权重。
方法 1
解决此挑战的最简单和最普遍的解决方案之一是利用子树的深度优先搜索 (DFS) 探索。在这种方法中，我们以深度优先的方式遍历给定节点的子树，在继续到下一个兄弟节点之前，访问每个节点及其后代。在每个节点处，我们评估其距根节点的距离，如果它在指定的限制范围内，我们修改迄今为止发现的最小权重。这种方法的时间复杂度为 O(n)，其中 n 表示子树中的节点数，因为每个节点仅访问一次。
示例
提供的代码构成一个程序，旨在确定二叉树中距离节点“X”最多为“d”的子树中节点的最小权重。二叉树由称为“Node”的结构表示，该结构包含权重、对其左孩子的引用以及对其右孩子的引用。
主函数“findMinimumWeightDFS”以节点“x”和整数“d”作为输入，并返回距离“x”最多为“d”的节点的最小权重。该函数使用辅助函数“findMinimumWeightDFS”在二叉树上执行深度优先搜索 (DFS) 并更新迄今为止发现的最小权重。
最小权重初始化为一个较大的值，并在 DFS 探索期间修改，如果当前节点距离根节点最多为“d”。该函数在 DFS 探索后返回找到的最终最小权重。
#include <iostream>
#include <climits>
using namespace std;
// Definition of Node structure
struct Node {
int weight;
Node* left;
Node* right;
Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};
// Function to perform DFS traversal and find minimum weight
void findMinimumWeightDFS(Node* x, int d, int distance, int& minWeight) {
// Base case: if the current node is null or distance exceeds D, return
if (x == nullptr || distance > d) {
return;
}
// If the current node is at most D-distant from the root node, update minWeight
if (distance <= d) {
minWeight = min(minWeight, x->weight);
}
// Recursively perform DFS on the left and right children of the current node
findMinimumWeightDFS(x->left, d, distance + 1, minWeight);
findMinimumWeightDFS(x->right, d, distance + 1, minWeight);
}
// Function to find minimum weight from subtree of at most D-distant nodes from node X using DFS
int findMinimumWeightDFS(Node* x, int d) {
int minWeight = INT_MAX; // Initialize minWeight to a large value
findMinimumWeightDFS(x, d, 0, minWeight); // Perform DFS traversal
return minWeight; // Return the minimum weight obtained
}
// Driver code
int main() {
// Create a sample binary tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Test the findMinimumWeightDFS function
int d = 2;
int minWeight = findMinimumWeightDFS(root, d);
cout << "Minimum weight from subtree of at most " << d << "-distant nodes from node X: " << minWeight << endl;
return 0;
}
输出
Minimum weight from subtree of at most 2-distant nodes from node X: 1
方法 2
解决此挑战的另一种策略是使用子树的广度优先搜索 (BFS) 探索。在这种方法中，我们以广度优先的方式遍历给定节点的子树，在继续到下一层之前，访问节点的所有后代。在每个节点处，我们评估其距根节点的距离，如果它在指定的限制范围内，我们修改迄今为止发现的最小权重。这种方法的时间复杂度为 O(n)，其中 n 表示子树中的节点数，因为每个节点仅访问一次。但是，这种方法的空间复杂度大于 DFS 方法，因为它需要一个队列来跟踪要探索的节点。
示例
该代码构成一个程序，旨在确定二叉树中节点的最小权重，给定距根节点的最大距离“d”。该策略涉及对二叉树进行广度优先搜索 (BFS) 探索，并将每个节点及其距根节点的距离存储在一个队列中。该函数以根节点及其距离为 0 开始，并将其添加到队列中。
然后，它迭代地从队列的前面检索节点，如果节点的距离最多为“d”，则更新最小权重。如果节点具有左或右后代，则将子节点添加到队列中，并更新距离。该函数继续执行，直到队列为空。最后，该函数返回从 BFS 探索中获得的最小权重。
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
// Definition of Node structure
struct Node {
int weight;
Node* left;
Node* right;
Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};
// Function to perform BFS traversal and find minimum weight
int findMinimumWeightBFS(Node* x, int d) {
queue<pair<Node*, int>>q; // Create a queue to store nodes and their distances
q.push({x, 0}); // Push the root node and its distance (0) to the queue
int minWeight = INT_MAX; // Initialize minWeight to a large value
while (!q.empty()) {
Node* curr = q.front().first; // Get the current node from the front of the queue
int distance = q.front().second; // Get the distance of the current node from the root
q.pop(); // Pop the current node from the queue
// If the current node is at most D-distant from the root node, update minWeight
if (distance <= d) {
minWeight = min(minWeight, curr->weight);
}
// If the current node has left child, push it to the queue with updated distance
if (curr->left) {
q.push({curr->left, distance + 1});
}
// If the current node has right child, push it to the queue with updated distance
if (curr->right) {
q.push({curr->right, distance + 1});
}
}
return minWeight; // Return the minimum weight obtained
}
// Driver code
int main() {
// Create a sample binary tree
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Test the findMinimumWeightBFS function
int d = 2;
int minWeight = findMinimumWeightBFS(root, d);
cout << "Minimum weight from subtree of at most " << d << "-distant nodes from node X: " << minWeight << endl;
return 0;
}
输出
Minimum weight from subtree of at most 2-distant nodes from node X: 1
结论
本文介绍了如何使用 C++ 获取二叉树中距离特定节点 X 最多为 D 的节点的子树的最小权重。我们研究了深度优先搜索 (DFS) 和广度优先搜索 (BFS) 方法，并为每种方法提供了实现代码和示例结果。
82 次浏览
