Die Anzahl gleichschenkliger Dreiecke in einem Binärbaum

Ein Binärbaum ist eine Datenstruktur, in der jeder Knoten bis zu zwei untergeordnete Knoten haben kann. Diese Kinder werden linke Kinder bzw. rechte Kinder genannt. Angenommen, wir erhalten eine übergeordnete Array-Darstellung, Sie müssen diese verwenden, um einen Binärbaum zu erstellen. Ein Binärbaum kann mehrere gleichschenklige Dreiecke haben. Wir müssen die Gesamtzahl der möglichen gleichschenkligen Dreiecke in diesem Binärbaum ermitteln.

In diesem Artikel werden wir verschiedene Techniken zur Lösung dieses Problems in C++ untersuchen.

Das Problem verstehen

Gibt Ihnen ein übergeordnetes Array. Sie müssen es in Form eines Binärbaums darstellen, sodass der Array-Index den Wert des Baumknotens bildet und der Wert im Array den übergeordneten Knoten dieses bestimmten Index angibt.

Bitte beachten Sie, dass -1 immer der übergeordnete Root-Knoten ist. Nachfolgend finden Sie ein Array und seine binäre Baumdarstellung.

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

Binärbaum -

In jedem Binärbaum können wir drei Arten gleichschenkliger Dreiecke haben -

• Linkes gleichschenkliges Dreieck − In diesem Dreieck ist der Scheitelpunkt ein untergeordneter Knoten des linken übergeordneten Knotens, und die Scheitelpunkte, die die Basis bilden (beide Seiten des gleichschenkligen Dreiecks), sind links untergeordneter Knoten. Untergeordnete Knoten können direkt oder indirekt sein. Im Baum oben haben wir zwei solcher gleichschenkligen Dreiecke – (2, 6, 3), (3, 7, 1).

• Rechtsgleichschenkliges Dreieck − In diesem Dreieck ist der Scheitelpunkt das rechte Kind des Elternteils, während der Scheitelpunkt, der die Basis bildet, das rechte Kind des Scheitelpunkts ist. Kinder können direkt oder indirekt sein. Im Baum oben haben wir nur ein solches gleichschenkliges Dreieck (4, 1, 8).

• Ausgeglichenes gleichschenkliges Dreieck − In diesem Dreieck sind die Scheitelpunkte, die die Basis bilden, die linken und rechten untergeordneten Knoten des Scheitelpunktknotens. Im obigen Baum haben wir fünf solcher gleichschenkligen Dreiecke (1, 3, 4), (3, 2, 7), (4, 8, 9), (2, 5, 6), (1, 2, 9).

Für den obigen Binärbaum haben wir also insgesamt 8 gleichschenklige Dreiecke.

Durchquerung mit Tiefensuche

Depth First Search (DFS) ist eine Methode zum Tiefendurchsuchen aller Knoten eines Baums. Es beginnt am Wurzelknoten, bewegt sich zu jedem Zweig und geht dann zurück.

• Zuerst verwenden wir DFS, um jeden Knoten des Binärbaums zu durchlaufen und ihn in ein Diagramm umzuwandeln, sodass jeder Knoten als nebeneinander dargestellt dargestellt wird. Dies erleichtert die Durchquerung.

• Für jeden Knoten prüfen wir, ob er untergeordnete Knoten hat. Nach der Überprüfung sortieren wir sie mit der Funktion sort(node[x].begin(), node[x].end()).

• Als nächstes prüfen wir, ob der aktuelle Knoten der linke oder rechte Nachfolger seines entsprechenden übergeordneten Knotens ist. Wir verwenden die DFS-Funktion rekursiv auf allen Knoten des Binärbaums.

• Wenn der aktuelle Knoten zwei Kinder hat (direkt oder indirekt), prüfen wir die Möglichkeit, dass ein gleichschenkliges Dreieck existiert, indem wir die Kanten zwischen ihnen berechnen. Wir finden die Kanten zwischen ihnen mithilfe der Funktion graph, die im folgenden Code angegeben ist.

• Abschließend berechnen wir die Gesamtzahl der gleichschenkligen Dreiecke, indem wir alle möglichen Dreiecke in verschiedenen Positionen addieren.

Beispiel

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

Ausgabe

Number of isosceles triangles in the binary tree are 8

Fazit

Wir haben besprochen, wie man die Gesamtzahl der gleichseitigen Dreiecke in einem Binärbaum ermittelt, wenn ein übergeordnetes Array gegeben ist. Wir können dies erreichen, indem wir die Tiefensuche verwenden, die es uns ermöglicht, einen Binärbaum zu durchlaufen.

Das obige ist der detaillierte Inhalt vonDie Anzahl gleichschenkliger Dreiecke in einem Binärbaum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!