Trouver le plus grand sous-arbre de recherche binaire dans un arbre binaire donné

Dans ce problème, on nous donne un arbre binaire BT. Notre tâche est detrouver le plus grand sous-arbre de recherche binairedans un arbre binaire donné.

L'arbre binaire est une structure de données spéciale utilisée pour le stockage de données. Les arbres binaires ont une condition spéciale selon laquelle chaque nœud peut avoir au plus deux nœuds enfants.

L'arbre de recherche binaire (BST) est un arbre qui satisfait aux propriétés suivantes :

La valeur clé du sous-arbre gauche est plus petite que la valeur clé de son nœud parent (nœud racine).
La valeur clé du sous-arbre droit est supérieure ou égale à la valeur clé de son nœud parent (nœud racine).

Prenons un exemple pour comprendre ce problème,

Entrée :

在给定的二叉树中找到最大的二叉搜索子树 - C++中的第1集

Sortie : 3

Explication

Full binary tree is a BST.

Copier après la connexion

Solution

La façon simple de résoudre le problème est de faire le arbre en cours Parcours de la commande. Pour chaque nœud de l'arbre, vérifiez si son sous-arbre est un arbre de recherche binaire. Enfin, la taille du plus grand sous-arbre de recherche binaire est renvoyée.

Exemple

Exemple de programme pour illustrer le fonctionnement de notre solution

#include 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 "<
        
         Copier après la connexion

Output

The size of the largest possible BST is 5

Copier après la connexion

Une autre approche

Une autre façon de résoudre ce problème est de parcourir l'arbre depuis le bas et de vérifier à travers ses nœuds enfants s'il s'agit bien de BST. Pour ce faire, nous suivrons les éléments suivants : Si

est BST.

Dans le cas du sous-arbre de gauche, la valeur du plus grand élément.
Dans le cas du sous-arbre de droite, la valeur du plus petit élément. Ces valeurs doivent être comparées au nœud actuel pour vérifier le BST.

De plus, la taille du BST maximum sera mise à jour en la comparant avec la taille du BST actuel.

Exemple

#include 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 findlargestBSTSizeRec(node* node, int *minValRsubTree, int *maxValLsubTree, int *maxBSTSize, bool *isBSTree) { if (node == NULL){ *isBSTree = true; return 0; } int min = INT_MAX; bool left_flag = false; bool right_flag = false; int leftSubtreeSize,rightSubTreeSize; *maxValLsubTree = INT_MIN; leftSubtreeSize = findlargestBSTSizeRec(node->left, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree); if (*isBSTree == true && node->data > *maxValLsubTree) left_flag = true; min = *minValRsubTree; *minValRsubTree = INT_MAX; rightSubTreeSize = findlargestBSTSizeRec(node->right, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree); if (*isBSTree == true && node->data < *minValRsubTree) right_flag = true; if (min < *minValRsubTree) *minValRsubTree = min; if (node->data < *minValRsubTree) *minValRsubTree = node->data; if (node->data > *maxValLsubTree) *maxValLsubTree = node->data; if(left_flag && right_flag){ if (leftSubtreeSize + rightSubTreeSize + 1 > *maxBSTSize) *maxBSTSize = (leftSubtreeSize + rightSubTreeSize + 1); return (leftSubtreeSize + rightSubTreeSize + 1); } else{ *isBSTree = false; return 0; } } int findlargestBSTSize(node* node){ int min = INT_MAX; int max = INT_MIN; int largestBSTSize = 0; bool isBST = false; findlargestBSTSizeRec(node, &min, &max, &largestBSTSize, &isBST); return largestBSTSize; } 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 BST is "<
        
         Copier après la connexion