資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++實現二叉樹中最大的二叉搜尋樹
在二叉樹中，每個子節點只有兩個節點（左節點和右節點）。樹結構只是資料的簡單表示。二叉搜尋樹 (BST) 是滿足以下條件的特殊型別的二叉樹：
左子節點的值小於其父節點的值
右子節點的值大於其父節點的值
假設我們給定一個二叉樹，我們需要找出其中最大的二叉搜尋樹 (BST)。
在這個任務中，我們將建立一個函式來查詢二叉樹中最大的 BST。當二叉樹本身就是一個 BST 時，可以確定整個二叉樹的大小。例如：
輸入
10 /\ 5 15 /\ \ 1 8 7
如圖所示，突出顯示的 BST 子樹是最大的。子樹的大小為'3'，所以返回值是子樹的大小。
輸入
52 / \ 37 67 /\ / \ 12 27 57 77 /\ 72 87
輸出
5
節點長度小於其父節點長度的子樹最多包含三個大小的 BST 節點。
查詢給定二叉樹中最大 BST 的方法
對於每個節點 x，如果以下幾點有效，則二叉樹為 BST。只有資料小於其父節點的資料的節點才會出現在節點的左子樹中。只能有一個節點的資料大於其父節點的資料。左右子樹都應該具有二叉搜尋樹 (BST) 的特徵。
演算法將是：
我們將從二叉樹的根節點開始，使用遞迴進行中序遍歷。對於當前節點“ROOT”，我們將執行以下操作：
如果它是有效 BST 的根節點，則返回其大小。
否則，我們將找到左子樹和右子樹中最大的 BST。
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *
newNode (int data) {
struct Node *node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
struct Detail {
int size;
int max;
int min;
int ans;
bool isBST;
};
bool isBST (Node * root, int min, int max) {
if (root == NULL) {
return true;
}
if (root->data < min || root->data > max) {
return false;
}
return isBST (root->left, min, root->data - 1) &&
isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
if (root == NULL) {
return 0;
}
return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
// Current Subtree is BST.
if (isBST (root, INT_MIN, INT_MAX) == true) {
return size (root);
}
// Find largest BST in left and right subtrees.
return max (largestBST (root->left), largestBST (root->right));
}
int main () {
struct Node *root = newNode (67);
root->left = newNode (72);
root->right = newNode (77); root->left->left = newNode (57);
printf ("Size of the largest BST is %d", largestBST (root));
return 0;
}輸出
Size of the largest BST is 2
結論
在這個問題中，我們學習了什麼是二叉樹和二叉搜尋樹，以及如何藉助遞迴在給定的二叉樹中找到最大的 BST。藉助遞迴，我們將找出每個節點下的子樹是否是 BST，並相應地返回值。
更新於：2022年3月7日
392 次瀏覽
廣告