在进行计算机编程时，有时需要求出源自特定节点的子树的最小权重，条件是该子树不能包含距离指定节点超过D个单位的节点。这个问题出现在各个领域和应用中，包括图论、基于树的算法和网络优化。
子树是较大树结构的子集，指定的节点作为子树的根节点。子树包含根节点的所有后代及其连接边。节点的权重是指分配给该节点的特定值，可以表示其重要性、重要性或其他相关指标。在这个问题中，目标是找到子树中所有节点中的最小权重，同时将子树限制在距离根节点最多D个单位的节点。
在下面的文章中，我们将深入研究从子树中挖掘最小权重的复杂性，该子树的边界不超过来自节点 X 的 D 距离节点。
方法
方法 1 - 深度优先搜索 (DFS)，解决此问题的最常见和最直接的方法之一是使用子树的深度优先搜索 (DFS) 遍历.
方法2 − 解决这个问题的另一种方法是使用广度优先搜索（BFS）遍历子树。
语法
下面的语法声明了一个名为findMinimumWeight的函数，它接受两个参数。第一个参数Node* x是指向二叉树中一个节点的指针，第二个参数int d是表示距离的整数。该函数返回一个整数minWeight。在给定的代码片段中没有指定从节点x开始的子树中找到最小权重的算法的实现。
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”距离的节点的最小权重。二叉树由称为“节点”的结构表示，该结构包含权重、对其左子节点的引用以及对其右子节点的引用。
主函数“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) 方法，并提供了每种方法的实现代码和示例结果。
