Cari subtree carian binari terbesar dalam pokok binari yang diberikan - Episod 1 dalam C++

Dalam masalah ini, kita diberikan pokok binari BT. Tugas kami ialah mencari subpokok carian binari terbesar dalam pokok binari yang diberikan.

Pokok binari ialah struktur data khas yang digunakan untuk penyimpanan data. Pokok binari mempunyai syarat khas yang setiap nod boleh mempunyai paling banyak dua nod anak.

Pokok Carian Binari (BST) ialah pokok yang memenuhi sifat berikut:

• Nilai utama subpokok kiri adalah lebih kecil daripada nilai kunci nod induknya (nod akar).

• Nilai utama subpokok kanan adalah lebih besar daripada atau sama dengan nilai kunci nod induknya (nod akar).

Mari kita ambil contoh untuk memahami masalah ini,

Input:

Output: 3

Penjelasan

Cara menyelesaikannya

mudah untuk melakukan pokok sedang berjalan Perintah traversal. Untuk setiap nod pokok, semak sama ada subpokoknya ialah pokok carian binari. Akhirnya, saiz subpokok carian binari terbesar dikembalikan.

Contoh

Contoh program untuk menggambarkan cara penyelesaian kami berfungsi

Full binary tree is a BST.

Output

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

Pendekatan lain

Cara lain untuk menyelesaikan masalah ini adalah dengan melintasi pokok itu dari bawah dan semak melalui anak pokoknya BST. Untuk melakukan ini, kami akan menjejaki perkara berikut: Sama ada

ialah BST.

• Dalam kes subpokok kiri, nilai elemen terbesar.

• Dalam kes subpokok kanan, nilai unsur terkecil. Nilai-nilai ini perlu dibandingkan dengan nod semasa untuk menyemak BST.

Selain itu, saiz BST maksimum akan dikemas kini dengan membandingkannya dengan saiz BST semasa.

Contoh

The size of the largest possible BST is 5

Output

#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 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 "<<findlargestBSTSize(root);
   return 0;
}

Atas ialah kandungan terperinci Cari subtree carian binari terbesar dalam pokok binari yang diberikan - Episod 1 dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!