Übersetzen Sie den größten BST in einem Binärbaum in C++

In einem Binärbaum hat jeder untergeordnete Knoten nur zwei Knoten (links und rechts). Eine Baumstruktur ist lediglich eine Darstellung von Daten. Ein binärer Suchbaum (BST) ist eine spezielle Art von Binärbaum, der diese Bedingungen erfüllt:

• Der linke untergeordnete Knoten ist kleiner im Vergleich zu seinem übergeordneten Knoten.

• Der übergeordnete Knoten des rechten untergeordneten Knotens ist größer als der untergeordnete Knoten Knoten

Angenommen, wir sollten bei einem gegebenen Binärbaum den größten binären Suchbaum (BST) finden.

In dieser Aufgabe erstellen wir eine Funktion, um den größten BST in einem Binärbaum zu finden. Wenn der Binärbaum selbst ein BST ist, kann die Größe des gesamten Binärbaums bestimmt werden. Beispiel:

Geben Sie

  10
  /\
 5  15
 /\  \
1  8  7

ein, wie im Bild gezeigt. In diesem Fall ist der hervorgehobene BST-Teilbaum der größte. „3“ ist die Größe des Teilbaums, daher ist der Rückgabewert die Größe des Teilbaums.

Eingabe

    52
    / \
   37 67
   /\ / \
 12 27 57 77
          /\
         72 87

Ausgabe

5

Ein Teilbaum, dessen Knotenlänge kleiner als die Länge seines Elternteils ist, hat höchstens drei BST-Knoten der Größe.

Methode zum Ermitteln der maximalen BST in einem gegebenen Binärbaum

Für jeden Knoten x ist ein Binärbaum ein BST, wenn die folgenden Punkte gültig sind. Im linken Teilbaum des Knotens werden nur Knoten angezeigt, deren Daten kleiner sind als die Daten ihres übergeordneten Knotens. Nur ein Knoten kann mehr Daten haben als sein übergeordneter Knoten. Sowohl der linke als auch der rechte Teilbaum sollten durch einen binären Suchbaum (BST) dargestellt werden.

Der Algorithmus wird sein:

Wir werden eine Inorder-Traversierung von einem Binärbaum aus durchführen und Rekursion verwenden. Für den aktuellen Knoten „ROOT“ werden wir Folgendes tun:

• Wenn es sich um die Wurzel eines gültigen BST handelt, geben wir seine Größe zurück.

• Ansonsten finden wir die maximale BST im linken und rechten Teilbaum.

Beispiel

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left;
   struct Node *right;
};
struct Node *
newNode (int data) {
   struct Node *node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
struct Detail {
   int size;
   int max;
   int min;
   int ans;
   bool isBST;
};
bool isBST (Node * root, int min, int max) {
   if (root == NULL) {
      return true;
   }
   if (root->data < min || root->data > max) {
      return false;
   }
   return isBST (root->left, min, root->data - 1) &&
   isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
   if (root == NULL) {
      return 0;
   }
   return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
   // Current Subtree is BST.
   if (isBST (root, INT_MIN, INT_MAX) == true) {
      return size (root);
   }
   // Find largest BST in left and right subtrees.
   return max (largestBST (root->left), largestBST (root->right));
}
int main () {
   struct Node *root = newNode (67);
   root->left = newNode (72);
   root->right = newNode (77); root->left->left = newNode (57);
   printf ("Size of the largest BST is %d", largestBST (root));
   return 0;
}

Ausgabe

Size of the largest BST is 2

Fazit

In dieser Frage haben wir gelernt, was Binärbäume und binäre Suchbäume sind und wie man mithilfe der Rekursion den größten BST in einem bestimmten Binärbaum findet. Mit Hilfe der Rekursion finden wir heraus, ob der Teilbaum unter jedem Knoten ein BST ist und geben den entsprechenden Wert zurück.

Das obige ist der detaillierte Inhalt vonÜbersetzen Sie den größten BST in einem Binärbaum in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!