查詢從節點X開始，距離最多為D的子樹中的最小權重

在進行電腦程式設計時，有時需要求出源自特定節點的子樹的最小權重，條件是該子樹不能包含距離指定節點超過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) 方法，并提供了每种方法的实现代码和示例结果。

以上是查詢從節點X開始，距離最多為D的子樹中的最小權重的詳細內容。更多資訊請關注PHP中文網其他相關文章！