Finden Sie den größten binären Suchteilbaum in einem bestimmten Binärbaum – Episode 1 in C++

In diesem Problem erhalten wir einen Binärbaum BT. Unsere Aufgabe besteht darin, den größten Teilbaum der binären Suche in einem bestimmten Binärbaum zu finden.

Binärbaum ist eine spezielle Datenstruktur, die zur Datenspeicherung verwendet wird. Bei Binärbäumen gilt die besondere Bedingung, dass jeder Knoten höchstens zwei untergeordnete Knoten haben kann.

Binary Search Tree (BST) ist ein Baum, der die folgenden Eigenschaften erfüllt:

• Der Schlüsselwert des linken Teilbaums ist kleiner als der Schlüsselwert seines übergeordneten Knotens (Wurzelknoten).

• Der Schlüsselwert des rechten Teilbaums ist größer oder gleich dem Schlüsselwert seines übergeordneten Knotens (Wurzelknoten).

Nehmen wir ein Beispiel, um dieses Problem zu verstehen:

Eingabe:

Ausgabe: 3

Erklärung

Full binary tree is a BST.

Lösung

Der einfache Weg, das Problem zu lösen ist das zu tun Baum in Bearbeitung Auftragsdurchlauf. Überprüfen Sie für jeden Knoten des Baums, ob sein Teilbaum ein binärer Suchbaum ist. Schließlich wird die Größe des größten Teilbaums der binären Suche zurückgegeben. 🔜 BST. Dazu verfolgen wir Folgendes: Ob

BST ist.

Im Fall des linken Teilbaums der Wert des größten Elements.

Im Fall des rechten Teilbaums der Wert des kleinsten Elements. Diese Werte müssen mit dem aktuellen Knoten verglichen werden, um den BST zu überprüfen.

Zusätzlich wird die Größe des maximalen BST aktualisiert, indem sie mit der Größe des aktuellen BST verglichen wird.

Beispiel

• #include<bits/stdc++.h>
  using namespace std;
  class node{
     public:
     int data;
     node* left;
     node* right;
     node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
     }
  };
  int findTreeSize(node* node) {
     if (node == NULL)
        return 0;
     else
        return(findTreeSize(node->left) + findTreeSize(node->right) + 1);
  }
  int isBSTree(struct node* node) {
     if (node == NULL)
        return 1;
     if (node->left != NULL && node->left->data > node->data)
        return 0;
     if (node->right != NULL && node->right->data < node->data)
        return 0;
     if (!isBSTree(node->left) || !isBSTree(node->right))
        return 0;
     return 1;
  }
  int findlargestBSTSize(struct node *root) {
     if (isBSTree(root)){
        return findTreeSize(root);
  }
  else
     return max(findlargestBSTSize(root->left), findlargestBSTSize(root->right));
  }
  int main() {
     node *root = new node(5);
     root->left = new node(2);
     root->right = new node(8);
     root->left->left = new node(1);
     root->left->right = new node(4);
     cout<<"The size of the largest possible BST is "<<findlargestBSTSize(root);
     return 0;
  }

  Ausgabe

  The size of the largest possible BST is 5

  Das obige ist der detaillierte Inhalt vonFinden Sie den größten binären Suchteilbaum in einem bestimmten Binärbaum – Episode 1 in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!