在這個問題中,我們給定了一個二元樹BT。我們的任務是在給定的二元樹中找到最大的二元搜尋子樹。
二元樹是一種用於資料儲存的特殊資料結構。二元樹有一個特殊的條件,就是每個節點最多可以有兩個子節點。
二元搜尋樹(BST)是一棵滿足下列屬性的樹:
#左子樹的鍵值小於其父節點(根節點)的鍵值。
右子樹的鍵值大於或等於其父節點(根節點)的鍵值。
讓我們舉例來理解這個問題,
#輸入:
輸出:3
解釋
Full binary tree is a BST.
解決問題的簡單方法是對樹進行中序遍歷。對於樹的每個節點,檢查其子樹是否為二元搜尋樹。最後傳回最大的二元搜尋子樹的大小。
程式範例,說明我們解決方案的工作原理
#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; }
The size of the largest possible BST is 5
另一種方法
解決這個問題的另一種方法是從底部遍歷樹,並透過其子節點檢查是否為BST。為此,我們將追蹤以下內容:
是否為BST。
在左子樹的情況下,最大元素的值。
在右子樹的情況下,最小元素的值。這些值需要與目前節點進行比較以檢查BST。
此外,透過與目前BST的大小進行比較,最大BST的大小將會更新。
#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; }
The Size of the largest BST is 5
以上是在給定的二元樹中找到最大的二元搜尋子樹 - C++中的第1集的詳細內容。更多資訊請關注PHP中文網其他相關文章!