노드 X에서 시작하여 하위 트리의 최소 가중치와 최대 D의 거리를 쿼리합니다.

컴퓨터 프로그래밍을 할 때 특정 노드에서 발생하는 하위 트리의 최소 가중치를 찾아야 하는 경우가 있습니다. 단, 하위 트리에는 지정된 노드에서 D 단위 이상 떨어진 노드가 포함될 수 없습니다. 이 문제는 그래프 이론, 트리 기반 알고리즘, 네트워크 최적화 등 다양한 분야와 응용 분야에서 발생합니다.

하위 트리는 지정된 노드가 하위 트리의 루트 노드 역할을 하는 더 큰 트리 구조의 하위 집합입니다. 하위 트리에는 루트 노드의 모든 자손과 해당 연결 가장자리가 포함됩니다. 노드의 가중치는 해당 노드에 할당된 특정 값을 나타내며, 이는 해당 노드의 중요성, 중요도 또는 기타 관련 측정항목을 나타낼 수 있습니다. 이 문제의 목표는 루트 노드에서 최대 D 단위 떨어진 노드로 하위 트리를 제한하면서 하위 트리의 모든 노드 중에서 최소 가중치를 찾는 것입니다.

다음 기사에서는 경계가 노드 X에서 D 거리 노드를 넘지 않는 하위 트리에서 최소 가중치를 마이닝하는 복잡성을 자세히 살펴보겠습니다.

방법

• 방법 1 - 깊이 우선 검색(DFS), 이 문제를 해결하는 가장 일반적이고 간단한 방법 중 하나는 하위 트리의 깊이 우선 검색(DFS) 탐색을 사용하는 것입니다.

• 방법 2 − 이 문제를 해결하는 또 다른 방법은 BFS(너비 우선 탐색)를 사용하여 하위 트리를 탐색하는 것입니다.

문법

아래 구문은 두 개의 매개변수를 허용하는 findMinimumWeight라는 함수를 선언합니다. 첫 번째 매개변수 Node* x는 이진 트리의 노드에 대한 포인터이고, 두 번째 매개변수 int d는 거리를 나타내는 정수입니다. 이 함수는 정수 minWeight를 반환합니다. 노드 x에서 시작하는 하위 트리에서 최소 가중치를 찾는 알고리즘의 구현은 주어진 코드 조각에 지정되어 있지 않습니다.

으아악

어디 -

• Node* x는 트리의 루트 노드에 대한 포인터를 나타냅니다.

• int d는 하위 트리의 노드와 루트 노드 사이의 최대 거리 제약 조건을 나타냅니다.

알고리즘

컴퓨터 과학의 복잡한 과제는 주어진 노드 X에서 시작하여 D 노드 이하에 걸쳐 있는 하위 트리의 최소 가중치를 결정하는 것입니다. 이 문제를 해결하기 위한 몇 가지 알고리즘이 있습니다. 여기서는 접근 방식에 대한 높은 수준의 개요를 제공합니다 −

1단계 - 노드 X를 하위 트리의 루트로 시작합니다.

2단계 - 깊이 우선 방식으로 하위 트리를 순회하면서 루트 노드에서 각 노드의 거리를 주의 깊게 기록합니다.

3단계 - 지금까지 발생한 가장 작은 무게를 추적하는 변수를 유지합니다.

4단계 - 각 노드에서 루트 노드에서 해당 노드까지의 거리가 D 제한 내에 있는지 평가합니다. 그렇다면 현재 노드의 가중치를 사용하여 최소 가중치 변수를 업데이트합니다.

5단계 - 하위 트리의 모든 노드에 대해 3단계와 4단계를 반복합니다.

6단계 - 마지막으로 하위 트리에서 얻은 최소 가중치를 반환합니다.

방법 1

이 문제에 대한 가장 간단하고 일반적인 솔루션 중 하나는 하위 트리의 깊이 우선 검색(DFS) 탐색을 활용하는 것입니다. 이 접근 방식에서는 깊이 우선 방식으로 특정 노드의 하위 트리를 순회하여 다음 형제로 진행하기 전에 각 노드와 그 자손을 방문합니다. 각 노드에서 루트 노드로부터의 거리를 평가하고 지정된 제한 내에 있으면 지금까지 찾은 가장 작은 가중치를 수정합니다. 이 접근 방식의 실행 시간 복잡도는 O(n)입니다. 여기서 n은 각 노드가 한 번만 방문되므로 하위 트리의 노드 수를 나타냅니다.

예

제공된 코드는 이진 트리의 노드로부터 최대 "d" 거리에 있는 하위 트리의 노드의 최소 가중치를 결정하도록 설계된 프로그램을 구성합니다. 이진 트리는 가중치, 왼쪽 자식 노드에 대한 참조, 오른쪽 자식 노드에 대한 참조를 포함하는 "노드"라는 구조로 표현됩니다.

주 함수 "findMinimumWeightDFS"는 노드 "x"와 정수 "d"를 입력으로 사용하고 "x"에서 최대 "d" 거리에 있는 노드의 최소 가중치를 반환합니다. 이 함수는 이진 트리에서 깊이 우선 검색(DFS)을 수행하고 지금까지 찾은 최소 가중치를 업데이트하는 도우미 함수 "findMinimumWeightDFS"를 사용합니다.

최소 가중치는 더 큰 값으로 초기화되고 현재 노드가 루트 노드로부터 최대 'd' 거리에 있는 경우 DFS 탐색 중에 수정됩니다. 이 함수는 DFS 탐색 후 찾은 최종 최소 가중치를 반환합니다.

으아악

출력

으아악

방법 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) 方法，并提供了每种方法的实现代码和示例结果。

위 내용은 노드 X에서 시작하여 하위 트리의 최소 가중치와 최대 D의 거리를 쿼리합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!