Traduire le plus grand BST dans un arbre binaire en C++

Dans un arbre binaire, chaque nœud enfant n'a que deux nœuds (gauche et droit). Une structure arborescente n’est qu’une représentation de données. Un arbre de recherche binaire (BST) est un type spécial d'arbre binaire qui satisfait à ces conditions -

• Le nœud enfant gauche est plus petit que son parent

• Le nœud parent du nœud enfant droit est plus grand que l'enfant node

Supposons qu'étant donné un arbre binaire, nous devrions trouver le plus grand arbre de recherche binaire (BST).

Dans cette tâche, nous allons créer une fonction pour trouver le plus grand BST dans un arbre binaire. Lorsque l'arbre binaire lui-même est un BST, la taille de l'arbre binaire entier peut être déterminée. Par exemple -

Entrez

  10
  /\
 5  15
 /\  \
1  8  7

comme indiqué sur l'image, dans ce cas, le sous-arbre BST en surbrillance est le plus grand. « 3 » est la taille du sous-arbre, donc la valeur de retour est la taille du sous-arbre.

Input

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

Output

5

Un sous-arbre dont la longueur du nœud est inférieure à la longueur de son parent a au plus trois nœuds BST de taille.

Méthode pour trouver le BST maximum dans un arbre binaire donné

Pour chaque nœud x, un arbre binaire est un BST si les points suivants sont valides. Seuls les nœuds dont les données sont inférieures à celles de leur nœud parent apparaîtront dans le sous-arbre gauche du nœud. Un seul nœud peut avoir plus de données que son parent. Le sous-arbre gauche et le sous-arbre droit doivent être représentés par un arbre de recherche binaire (BST).

L'algorithme sera -

Nous ferons un parcours dans l'ordre à partir d'un arbre binaire et en utilisant la récursivité. Pour le nœud actuel "ROOT", nous ferons ce qui suit -

• S'il s'agit de la racine d'un BST valide, nous renverrons sa taille.

• Sinon, on retrouvera le BST maximum dans les sous-arbres gauche et droit.

Exemple

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

Sortie

Size of the largest BST is 2

Conclusion

Dans cette question, nous avons appris ce que sont les arbres binaires et les arbres de recherche binaires et comment trouver le plus grand BST dans un arbre binaire donné à l'aide de la récursivité. À l'aide de la récursion, nous découvrirons si le sous-arbre sous chaque nœud est un BST et renverrons la valeur correspondante.

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!