ノード X から始まるサブツリーの最小重みと最大 D の距離を照会します。

コンピュータ プログラミングを行う場合、特定のノードから D 単位以上離れたノードをサブツリーに含めることができないという条件で、特定のノードから生じるサブツリーの最小重みを見つける必要がある場合があります。指定されたノード。この問題は、グラフ理論、ツリーベースのアルゴリズム、ネットワーク最適化など、さまざまな分野やアプリケーションで発生します。

サブツリーは、指定されたノードがサブツリーのルート ノードとして機能する、より大きなツリー構造のサブセットです。サブツリーには、ルート ノードのすべての子孫とそれらの接続エッジが含まれます。ノードの重みは、そのノードに割り当てられた特定の値を指し、その重要性、重要性、またはその他の関連するメトリックを表すことができます。この問題の目標は、ルート ノードから最大 D 単位離れたノードにサブツリーを制限しながら、サブツリー内のすべてのノード間の最小重みを見つけることです。

次の記事では、境界がノード X から D ノードの距離以下にあるサブツリーから最小重みをマイニングする複雑さについて詳しく説明します。

＃＃＃方法＃＃＃

• 方法 1

  - 深さ優先検索 (DFS) この問題を解決する最も一般的で簡単な方法の 1 つは、サブツリーの深さ優先検索 (DFS) トラバーサルを使用することです。

• 方法 2

  -この問題を解決する別の方法は、幅優先検索 (BFS) を使用してサブツリーを走査することです。

  ＃＃＃文法＃＃＃
次の構文は、2 つのパラメーターを受け入れる findMinimumWeight という名前の関数を宣言します。最初のパラメータ Node* x はバイナリ ツリー内のノードへのポインタであり、2 番目のパラメータ int d は距離を表す整数です。この関数は整数 minWeight を返します。ノード x から始まるサブツリー内の最小重みを見つけるアルゴリズムの実装は、指定されたコード スニペットでは指定されていません。

リーリー ＃＃＃どこ -＃＃＃

Node* x は、ツリーのルート ノードへのポインタを表します。

int d は、サブツリー内のノードとルート ノード間の最大距離の制約を表します。

• ＃＃＃アルゴリズム＃＃＃
コンピュータ サイエンスにおける複雑な課題は、特定のノード X から始まり D 個のノードにまたがらないサブツリーの最小重みを決定することです。この問題を解決するためのアルゴリズムがいくつかあります。ここでは、アプローチの高レベルの概要を示します -

• ステップ 1
- ノード X をサブツリーのルートとして開始します。

ステップ 2

- 深さ優先の方法でサブツリーを走査し、ルート ノードから各ノードの距離を注意深く記録します。

ステップ 3 - これまでに発生した最小の重みを追跡するために変数を維持します。

ステップ 4 - 各ノードで、ルート ノードからそのノードまでの距離が D 制限内であるかどうかを評価します。その場合、現在のノードの重みを使用して最小重み変数を更新します。

ステップ 5 - サブツリー内のすべてのノードに対してステップ 3 と 4 を繰り返します。

ステップ 6 - 最後に、サブツリーから取得した最小重みを返します。

方法1 この課題に対する最も単純かつ一般的な解決策の 1 つは、サブツリーの深さ優先検索 (DFS) 探索を利用することです。このアプローチでは、深さ優先の方法で特定のノードのサブツリーをトラバースし、次の兄弟に進む前に各ノードとその子孫を訪問します。各ノードで、ルート ノードからの距離を評価し、指定された制限内にある場合は、これまでに見つかった最小の重みを変更します。このアプローチの実行時間の複雑さは O(n) です。各ノードは 1 回だけ訪問されるため、n はサブツリー内のノードの数を表します。

＃＃＃例＃＃＃

提供されたコードは、バイナリ ツリー内のノード "X" から最大 "d" 距離離れたサブツリー内のノードの最小重みを決定するように設計されたプログラムを構成します。バイナリ ツリーは、「ノード」と呼ばれる構造によって表されます。この構造には、重み、左の子ノードへの参照、および右の子ノードへの参照が含まれます。 メイン関数「findMinimumWeightDFS」は、ノード「x」と整数「d」を入力として受け取り、「x」から最大「d」距離離れたノードの最小重みを返します。この関数は、バイナリ ツリーに対して深さ優先検索 (DFS) を実行し、これまでに見つかった最小重みを更新するヘルパー関数「findMinimumWeightDFS」を使用します。

現在のノードがルート ノードから最大「d」距離にある場合、最小重みはより大きな値に初期化され、DFS 探索中に変更されます。この関数は、DFS 探索後に見つかった最終的な最小重みを返します。

リーリー ＃＃＃出力＃＃＃ リーリー

方法 2

この課題に対処する別の戦略は、幅優先検索 (BFS) を使用してサブツリーを探索することです。このアプローチでは、次のレベルに進む前に、指定されたノードのサブツリーを幅優先の方法で走査し、すべてのノードの子を訪問します。各ノードで、ルート ノードからの距離を評価し、指定された制限内にある場合は、これまでに見つかった最小重みを変更します。この方法の時間計算量は O(n) です。各ノードは 1 回だけ訪問されるため、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 中国語 Web サイトの他の関連記事を参照してください。