在給定的二元樹中找到最大的二元搜尋子樹

在給定的二元樹中找到最大的二元搜尋子樹 - C++中的第1集

WBOY

發布： 2023-08-31 15:33:07

轉載

642 人瀏覽過

在這個問題中，我們給定了一個二元樹BT。我們的任務是在給定的二元樹中找到最大的二元搜尋子樹。

二元樹是一種用於資料儲存的特殊資料結構。二元樹有一個特殊的條件，就是每個節點最多可以有兩個子節點。

二元搜尋樹（BST）是一棵滿足下列屬性的樹：

#左子樹的鍵值小於其父節點（根節點）的鍵值。
右子樹的鍵值大於或等於其父節點（根節點）的鍵值。

讓我們舉例來理解這個問題，

#輸入：

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

輸出：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;
}

登入後複製