Fragen Sie das Mindestgewicht im Teilbaum ab Knoten X und höchstens Abstand D ab

Bei der Computerprogrammierung ist es manchmal notwendig, das Mindestgewicht eines Teilbaums zu ermitteln, der von einem bestimmten Knoten stammt, vorausgesetzt, der Teilbaum darf keine Knoten enthalten, die mehr als D Einheiten vom angegebenen Knoten entfernt sind. Dieses Problem tritt in verschiedenen Bereichen und Anwendungen auf, darunter in der Graphentheorie, baumbasierten Algorithmen und der Netzwerkoptimierung.

Ein Teilbaum ist eine Teilmenge einer größeren Baumstruktur, wobei der angegebene Knoten als Wurzelknoten des Teilbaums dient. Ein Teilbaum enthält alle Nachkommen des Wurzelknotens und deren Verbindungskanten. Die Gewichtung eines Knotens bezieht sich auf einen bestimmten, diesem Knoten zugewiesenen Wert, der seine Wichtigkeit, Wichtigkeit oder andere relevante Metriken darstellen kann. Bei diesem Problem besteht das Ziel darin, das Mindestgewicht aller Knoten in einem Teilbaum zu ermitteln und gleichzeitig den Teilbaum auf Knoten zu beschränken, die höchstens D Einheiten vom Wurzelknoten entfernt sind.

Im folgenden Artikel werden wir uns mit der Komplexität des Minings des Mindestgewichts aus einem Teilbaum befassen, dessen Grenzen nicht mehr als D Knoten vom Knoten X entfernt sind.

Methode

• Methode 1 – Tiefensuche (Depth First Search, DFS). Eine der gebräuchlichsten und unkompliziertesten Möglichkeiten, dieses Problem zu lösen, ist die Verwendung einer Tiefensuche (Depth First Search, DFS) zum Durchqueren des Teilbaums.

• Methode 2 - Eine andere Möglichkeit, dieses Problem zu lösen, besteht darin, den Teilbaum mit der Breitensuche (Bready-First Search, BFS) zu durchqueren.

Grammatik

Die folgende Syntax deklariert eine Funktion namens findMinimumWeight, die zwei Parameter akzeptiert. Der erste Parameter Node* x ist ein Zeiger auf einen Knoten im Binärbaum und der zweite Parameter int d ist eine Ganzzahl, die den Abstand darstellt. Diese Funktion gibt eine Ganzzahl minWeight zurück. Die Implementierung des Algorithmus zum Ermitteln des Mindestgewichts im Teilbaum ab Knoten x ist im angegebenen Codeausschnitt nicht angegeben.

int findMinimumWeight(Node* x, int d) {
   // Implementation of the algorithm
   // ...
   return minWeight;
}

Wo -

• Node* x stellt einen Zeiger auf den Wurzelknoten des Baums dar.

• int d stellt die Einschränkung des maximalen Abstands zwischen dem Knoten im Teilbaum und dem Wurzelknoten dar.

Algorithmus

Eine komplexe Herausforderung in der Informatik besteht darin, das Mindestgewicht eines Teilbaums zu bestimmen, der von einem gegebenen Knoten X ausgeht und sich nicht über mehr als D Knoten erstreckt. Zur Lösung dieses Problems gibt es mehrere Algorithmen. Hier bieten wir einen allgemeinen Überblick über den Ansatz −

Schritt 1 – Beginnen Sie mit Knoten X als Wurzel des Teilbaums.

Schritt 2 – Durchqueren Sie den Teilbaum in der Tiefe zuerst und notieren Sie dabei sorgfältig den Abstand jedes Knotens vom Wurzelknoten.

Schritt 3 – Pflegen Sie eine Variable, um das kleinste bisher festgestellte Gewicht zu verfolgen.

Schritt 4 – Bewerten Sie an jedem Knoten, ob der Abstand vom Wurzelknoten zu diesem Knoten innerhalb der D-Grenze liegt. Wenn ja, aktualisieren Sie die Variable mit der Mindestgewichtung mithilfe der Gewichtung des aktuellen Knotens.

Schritt 5 – Wiederholen Sie die Schritte 3 und 4 für alle Knoten im Unterbaum.

Schritt 6 – Geben Sie abschließend das vom Teilbaum erhaltene Mindestgewicht zurück.

Methode 1

Eine der einfachsten und gebräuchlichsten Lösungen für diese Herausforderung besteht darin, Teilbäume mithilfe der Tiefensuche (DFS) zu erkunden. Bei diesem Ansatz durchqueren wir den Teilbaum eines bestimmten Knotens auf eine Tiefen-zuerst-Methode und besuchen jeden Knoten und seine Nachkommen, bevor wir zum nächsten Geschwisterknoten übergehen. An jedem Knoten bewerten wir seinen Abstand vom Wurzelknoten, und wenn er innerhalb der angegebenen Grenzen liegt, ändern wir das kleinste bisher gefundene Gewicht. Die Laufzeitkomplexität dieses Ansatzes beträgt O(n), wobei n die Anzahl der Knoten im Teilbaum darstellt, da jeder Knoten nur einmal besucht wird.

Beispiel

Der bereitgestellte Code stellt ein Programm dar, das entwickelt wurde, um das Mindestgewicht eines Knotens in einem Teilbaum zu bestimmen, der höchstens „d“ von einem Knoten in einem Binärbaum entfernt ist. Ein Binärbaum wird durch eine Struktur namens „Knoten“ dargestellt, die eine Gewichtung, eine Referenz auf seinen linken untergeordneten Knoten und eine Referenz auf seinen rechten untergeordneten Knoten enthält.

Die Hauptfunktion „findMinimumWeightDFS“ verwendet den Knoten „x“ und eine Ganzzahl „d“ als Eingabe und gibt das Mindestgewicht des Knotens zurück, der höchstens „d“ von „x“ entfernt ist. Diese Funktion verwendet die Hilfsfunktion „findMinimumWeightDFS“, die eine Tiefensuche (DFS) im Binärbaum durchführt und das bisher gefundene Mindestgewicht aktualisiert.

Das Mindestgewicht wird auf einen größeren Wert initialisiert und während der DFS-Erkundung geändert, wenn der aktuelle Knoten höchstens „d“ vom Wurzelknoten entfernt ist. Diese Funktion gibt das endgültige Mindestgewicht zurück, das nach der DFS-Erkundung gefunden wurde.

#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;
}

Ausgabe

Minimum weight from subtree of at most 2-distant nodes from node X: 1

Methode 2

Eine weitere Strategie zur Bewältigung dieser Herausforderung besteht darin, die Breitensuche (Bready-First Search, BFS) zum Erkunden von Teilbäumen einzusetzen. Bei diesem Ansatz durchqueren wir den Teilbaum eines bestimmten Knotens in der Breite zuerst und besuchen alle untergeordneten Knoten des Knotens, bevor wir zur nächsten Ebene übergehen. An jedem Knoten bewerten wir seinen Abstand vom Wurzelknoten, und wenn er innerhalb der angegebenen Grenzen liegt, ändern wir das kleinste bisher gefundene Gewicht. Die zeitliche Komplexität dieser Methode beträgt O(n), wobei n die Anzahl der Knoten im Teilbaum darstellt, da jeder Knoten nur einmal besucht wird. Die räumliche Komplexität dieser Methode ist jedoch größer als bei der Methode der Tiefensuche (DFS), da eine Warteschlange erforderlich ist, um den Überblick über die zu erkundenden Knoten zu behalten.

示例

该代码构成了一个程序，旨在确定二叉树中节点的最小权重，给定距根节点的最大距离“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) 方法，并提供了每种方法的实现代码和示例结果。

Das obige ist der detaillierte Inhalt vonFragen Sie das Mindestgewicht im Teilbaum ab Knoten X und höchstens Abstand D ab. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!