Interrogez le poids minimum dans le sous-arbre à partir du nœud X et la distance au plus D

Lors de la programmation informatique, il est parfois nécessaire de trouver le poids minimum d'un sous-arbre provenant d'un nœud spécifique, à condition que le sous-arbre ne puisse pas contenir de nœuds éloignés de plus de D unités du nœud spécifié. Ce problème se pose dans divers domaines et applications, notamment la théorie des graphes, les algorithmes arborescents et l'optimisation des réseaux.

Un sous-arbre est un sous-ensemble d'une structure arborescente plus grande, avec le nœud spécifié servant de nœud racine du sous-arbre. Un sous-arbre contient tous les descendants du nœud racine et leurs arêtes de connexion. Le poids d'un nœud fait référence à une valeur spécifique attribuée à ce nœud, qui peut représenter son importance, son importance ou d'autres mesures pertinentes. Dans ce problème, l’objectif est de trouver le poids minimum parmi tous les nœuds d’un sous-arbre tout en limitant le sous-arbre aux nœuds situés au plus à D unités du nœud racine.

Dans l'article suivant, nous approfondirons la complexité de l'extraction du poids minimum d'un sous-arbre dont les limites ne sont pas supérieures à D distances entre les nœuds et le nœud X.

Méthode

• Méthode 1 - Recherche en profondeur d'abord (DFS), l'un des moyens les plus courants et les plus simples de résoudre ce problème consiste à utiliser une traversée de recherche en profondeur (DFS) du sous-arbre.

• Méthode 2 - Une autre façon de résoudre ce problème consiste à utiliser la recherche en largeur d'abord (BFS) pour parcourir le sous-arbre.

Grammaire

La syntaxe ci-dessous déclare une fonction appelée findMinimumWeight, qui accepte deux paramètres. Le premier paramètre Node* x est un pointeur vers un nœud dans l'arbre binaire, et le deuxième paramètre int d est un entier représentant la distance. Cette fonction renvoie un minWeight entier. L'implémentation de l'algorithme pour trouver le poids minimum dans le sous-arbre à partir du nœud x n'est pas spécifiée dans l'extrait de code donné.

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

Où -

• Node* x représente un pointeur vers le nœud racine de l'arborescence.

• int d représente la contrainte de distance maximale entre le nœud du sous-arbre et le nœud racine.

Algorithme

Un défi complexe en informatique consiste à déterminer le poids minimum d'un sous-arbre à partir d'un nœud X donné et ne s'étendant pas plus de nœuds D. Il existe plusieurs algorithmes pour résoudre ce problème. Nous fournissons ici un aperçu de haut niveau de l'approche −

Étape 1 - Commencez avec le nœud X comme racine du sous-arbre.

Étape 2 - Parcourez le sous-arbre en profondeur d'abord, en enregistrant soigneusement la distance de chaque nœud par rapport au nœud racine.

Étape 3 - Maintenez une variable pour suivre le plus petit poids rencontré jusqu'à présent.

Étape 4 - À chaque nœud, évaluez si la distance entre le nœud racine et ce nœud est dans la limite D. Si tel est le cas, mettez à jour la variable de poids minimum en utilisant le poids du nœud actuel.

Étape 5 - Répétez les étapes 3 et 4 pour tous les nœuds du sous-arbre.

Étape 6 - Enfin, renvoyez le poids minimum obtenu à partir du sous-arbre.

Méthode 1

L'une des solutions les plus simples et les plus courantes à ce défi consiste à exploiter l'exploration des sous-arbres par recherche en profondeur (DFS). Dans cette approche, nous parcourons le sous-arbre d'un nœud donné en profondeur, en visitant chaque nœud et ses descendants avant de passer au frère suivant. À chaque nœud, nous évaluons sa distance par rapport au nœud racine, et si elle tombe dans les limites spécifiées, nous modifions le plus petit poids trouvé jusqu'à présent. La complexité du temps d'exécution de cette approche est O(n), où n représente le nombre de nœuds dans le sous-arbre, puisque chaque nœud n'est visité qu'une seule fois.

Exemple

Le code fourni constitue un programme conçu pour déterminer le poids minimum d'un nœud dans un sous-arbre qui se trouve à une distance d'au plus "d" d'un nœud dans un arbre binaire. Un arbre binaire est représenté par une structure appelée « nœud », qui contient un poids, une référence à son nœud enfant gauche et une référence à son nœud enfant droit.

La fonction principale "findMinimumWeightDFS" prend le nœud "x" et un entier "d" en entrée et renvoie le poids minimum du nœud qui se trouve au plus à "d" de "x". Cette fonction utilise la fonction d'assistance "findMinimumWeightDFS", qui effectue une recherche en profondeur d'abord (DFS) sur l'arbre binaire et met à jour le poids minimum trouvé jusqu'à présent.

Le poids minimum est initialisé à une valeur plus grande et modifié lors de l'exploration DFS si le nœud actuel est au plus à une distance « d » du nœud racine. Cette fonction renvoie le poids minimum final trouvé après l'exploration 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;
}

Sortie

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

Méthode 2

Une autre stratégie pour relever ce défi consiste à utiliser la recherche en largeur d'abord (BFS) pour explorer les sous-arbres. Dans cette approche, nous parcourons le sous-arbre d'un nœud donné dans le sens de la largeur, en visitant tous les enfants du nœud avant de passer au niveau suivant. A chaque nœud, nous évaluons sa distance au nœud racine, et si elle est dans les limites spécifiées, nous modifions le plus petit poids trouvé jusqu'à présent. La complexité temporelle de cette méthode est O(n), où n représente le nombre de nœuds dans le sous-arbre, puisque chaque nœud n'est visité qu'une seule fois. Cependant, la complexité spatiale de cette méthode est plus grande que celle de la méthode de recherche en profondeur d'abord (DFS), car elle nécessite une file d'attente pour garder la trace des nœuds à explorer.

示例

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!