Le nombre de triangles isocèles dans un arbre binaire

Un arbre binaire est une structure de données dans laquelle chaque nœud peut avoir jusqu'à deux nœuds enfants. Ces enfants sont appelés respectivement enfants de gauche et enfants de droite. Supposons que nous recevions une représentation de tableau parent, vous devez l'utiliser pour créer un arbre binaire. Un arbre binaire peut avoir plusieurs triangles isocèles. Nous devons trouver le nombre total de triangles isocèles possibles dans cet arbre binaire.

Dans cet article, nous explorerons plusieurs techniques pour résoudre ce problème en C++.

Comprendre le problème

Vous donne un tableau parent. Vous devez le représenter sous la forme d'un arbre binaire afin que l'index du tableau forme la valeur du nœud de l'arbre et que la valeur dans le tableau donne le nœud parent de cet index particulier.

Veuillez noter que -1 est toujours le nœud parent racine. Vous trouverez ci-dessous un tableau et sa représentation arborescente binaire.

Parent array = [0, -1, 3, 1, 1, 2, 2, 3, 4, 4]

Arbre binaire -

Dans n'importe quel arbre binaire, nous pouvons avoir trois types de triangles isocèles -

• Triangle isocèle gauche − Dans ce triangle, le sommet est un nœud enfant du nœud parent gauche , et les sommets qui forment la base (les deux côtés du triangle isocèle) sont à gauche nœud enfant. Les nœuds enfants peuvent être directs ou indirects. Dans l'arbre ci-dessus, nous avons deux de ces triangles isocèles - (2, 6, 3), (3, 7, 1).

• Triangle isocèle droit − Dans ce triangle, le sommet est le droit enfant du parent, tandis que le sommet formant la base est l'enfant droit du sommet. Les enfants peuvent être directs ou indirects. Dans l’arbre ci-dessus, nous n’avons qu’un seul de ces triangles isocèles (4, 1, 8).

• Triangle isocèle équilibré − Dans ce triangle, les sommets qui forment la base sont les nœuds enfants gauche et droit du nœud sommet. Dans l'arbre ci-dessus, nous avons cinq de ces triangles isocèles (1, 3, 4), (3, 2, 7), (4, 8, 9), (2, 5, 6), (1, 2, 9).

Donc, pour l'arbre binaire ci-dessus, nous avons un total de 8 triangles isocèles.

Traversée utilisant la recherche en profondeur d'abord

Depth First Search(DFS) est une méthode permettant de parcourir tous les nœuds d'un arbre de manière approfondie. Il commence au nœud racine, se déplace vers chaque branche, puis revient en arrière.

• Tout d'abord, nous utilisons DFS pour parcourir chaque nœud de l'arbre binaire et le convertir en un graphique afin que chaque nœud soit représenté comme adjacent les uns aux autres. Cela facilite la traversée.

• Pour chaque nœud, nous vérifions s'il a des nœuds enfants. Après vérification, nous les trions à l'aide de la fonction sort(node[x].begin(), node[x].end()).

• Ensuite, nous vérifions si le nœud actuel est le successeur gauche ou droit de son nœud parent correspondant. Nous utilisons la fonction DFS de manière récursive sur tous les nœuds de l'arbre binaire.

• Si le nœud courant a deux enfants (directs ou indirects), on vérifie la possibilité qu'un triangle isocèle existe en calculant les arêtes entre eux. Nous retrouverons les arêtes entre eux grâce à la fonction graph donnée dans le code ci-dessous.

• Enfin, nous calculons le nombre total de triangles isocèles en additionnant tous les triangles possibles dans différentes positions.

Exemple

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX int(1e5)
vector < int > * node;
int right_down[MAX];
int right_up[MAX];
int left_down[MAX];
int left_up[MAX];

// DFS traversal over a node
void DFS(int x, int * parent) {
   // Check if adjacent nodes are present for node x
   if (node[x].size() != 0)
      sort(node[x].begin(), node[x].end());

   // Check whether the node has a parent node
   if (parent[x] != -1) {
      int indexOfParent = parent[x];
      int childrenCount = node[indexOfParent].size();

      if (childrenCount > 1) {
         int parentFirstChild = node[indexOfParent][0];

         // Check if current node is left node of the parent
         if (x == parentFirstChild) {
            right_up[x] += right_up[indexOfParent] + 1;
            // Check if current node is right node of the parent  
         } else {
            left_up[x] += left_up[indexOfParent] + 1;
         }
      } else {
         right_up[x] += right_up[indexOfParent] + 1;
      }
   }

   // Iterate over children of current node  
   for (int i = 0; i < node[x].size(); ++i) {
      int y = node[x][i];
      DFS(y, parent);

      // left child of current node
      if (i == 0) {
         left_down[x] += left_down[y] + 1;
      }
      // right child of current node
      else {
         right_down[x] += right_down[y] + 1;
      }
   }
}

int graph(int * parent, int N) {
   int rootNode;
   node = new vector < int > [N];

   for (int i = 0; i < N; ++i) {
      if (parent[i] != -1) {
         node[parent[i]].push_back(i);
      } else {
         rootNode = i;
      }

      left_up[i] = 0;
      right_up[i] = 0;
      left_down[i] = 0;
      right_down[i] = 0;
   }
   return rootNode;
}

int main() {
   int N = 10;
   int parent[] = { 0, -1, 3, 1, 1, 2, 2, 3, 4, 4 };
   int rootNode = graph(parent, N);
   DFS(rootNode, parent);
   int count = 0;
   // Counting the total isosceles triangles
   for (int i = 0; i < N; ++i) {
      count += min(right_down[i], right_up[i]);
      count += min(left_down[i], left_up[i]);
      count += min(left_down[i], right_down[i]);
   }
   cout << "Number of isosceles triangles in the binary tree are " <<
      count;
   return 0;
}

Sortie

Number of isosceles triangles in the binary tree are 8

Conclusion

Nous avons expliqué comment trouver le nombre total de triangles équilatéraux dans un arbre binaire lorsqu'on lui donne un tableau parent. Nous pouvons y parvenir en utilisant la recherche en profondeur d'abord, qui nous permet de parcourir un arbre binaire.

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!