Trong một cây nhị phân, mỗi nút con chỉ có hai nút (trái và phải). Cấu trúc cây đơn giản là biểu diễn dữ liệu. Cây tìm kiếm nhị phân (BST) là loại đặc biệt của cây nhị phân đáp ứng các điều kiện sau:
Nút con bên trái nhỏ hơn nút cha so với cha của nó
Nút cha của nút con bên phải lớn hơn nút con
Giả sử chúng ta được cho một cây nhị phân, và chúng ta cần tìm cây tìm kiếm nhị phân (BST) lớn nhất bên trong nó.
Trong nhiệm vụ này, chúng ta sẽ tạo một hàm để tìm BST lớn nhất trong cây nhị phân. Khi chính cây nhị phân là một BST, có thể xác định kích thước của toàn bộ cây nhị phân. Ví dụ:
Đầu vào
10 /\ 5 15 /\ \ 1 8 7
Như hình, cây con BST được làm nổi bật, trong trường hợp này, là lớn nhất. '3' là kích thước của cây con, vì vậy giá trị trả về là kích thước của cây con.
Đầu vào
52 / \ 37 67 /\ / \ 12 27 57 77 /\ 72 87
Đầu ra
5
Các cây con với nút có độ dài nhỏ hơn độ dài nút cha của chúng có lên đến ba nút BST.
Cách tiếp cận để tìm BST lớn nhất trong cây nhị phân cho trước
Đối với mọi nút x, một cây nhị phân là BST nếu các điểm sau hợp lệ. Chỉ có các nút có dữ liệu nhỏ hơn nút cha của chúng mới xuất hiện trong cây con trái của một nút. Chỉ có thể có một nút có dữ liệu nhiều hơn nút cha của nó. Cả cây con trái và phải đều phải được đặc trưng bởi cây tìm kiếm nhị phân (BST).
Thuật toán sẽ là −
Chúng ta sẽ bắt đầu từ gốc của cây nhị phân và thực hiện duyệt in-order bằng đệ quy. Với nút hiện tại 'ROOT', chúng ta sẽ làm như sau:
Nếu nó là gốc của một BST hợp lệ, ta trả về kích thước của nó.
Ngược lại, ta sẽ tìm BST lớn nhất trong cây con trái và phải.
Ví dụ
#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) { // Cây con hiện tại là BST. if (isBST (root, INT_MIN, INT_MAX) == true) { return size (root); } // Tìm BST lớn nhất trong cây con trái và phải. 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 ("Kích thước BST lớn nhất là %d", largestBST (root)); return 0; }Đầu ra
Kích thước BST lớn nhất là 2
Kết luận
Trong bài toán này, chúng ta đã học cây nhị phân & cây tìm kiếm nhị phân là gì và cách tìm BST lớn nhất trong cây nhị phân cho trước với sự giúp đỡ của đệ quy. Với sự giúp đỡ của đệ quy, chúng ta sẽ tìm xem cây con dưới mỗi nút có phải BST hay không và trả về giá trị tương ứng.