資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
