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

Dalam masalah ini, kita diberikan pokok binari BT. Tugas kami ialahmencari subpokok carian binari terbesardalam 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

Full binary tree is a BST.

#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 "<
         

          Salin selepas log masuk
         
        

Pendekatan lain

• 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.

The size of the largest possible BST is 5

Salin selepas log masuk

#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 "<
         

          Salin selepas log masuk
         
        

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!