"min" và "max" trong hàm này để kiểm tra xem cây nhị phân có phải là BST hợp lệ không?

Question

Mã bên dưới là từ Finding if a Binary Tree is a Binary Search Tree.

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{ 
    if(node == null) 
    return true; 

    if(node.element > MIN 
     && node.element < MAX 
     && IsValidBST(node.left,MIN,node.element) 
     && IsValidBST(node.right,node.element,MAX)) 
     return true; 
    else 
     return false; 
} 

Làm cách nào để sử dụng MIN và MAX? Họ đại diện cho những giá trị nào? Và tại sao họ cần được truyền qua chức năng?

Answer 1

Chúng phải được chuyển qua hàm để nó được gọi đệ quy với các dải giảm ngày càng tăng vì nó ở đây.

Tất nhiên, đối với cuộc gọi đầu tiên, bạn có thể xác định MIN và MAX từ cây, nhưng đối với những người tiếp theo bạn phải vượt qua như thế này.

Answer 2

[MIN, MAX] thể hiện phạm vi trong đó giá trị hợp lệ trong nút hiện tại có thể là. Đối với nút đầu tiên, INT_MIN và INT_MAX vì nó có thể có giá trị tùy ý, nhưng đối với con của nó, chúng ta cần kiểm tra thuộc tính BST - tất cả các con bên trái không được lớn hơn nút hiện tại và tất cả các nút bên phải không được nhỏ hơn . Đó là lý do tại sao chúng tôi thay đổi giá trị MIN và MAX cho chúng một cách tôn trọng.

Chú ý: nếu trong cây bạn có thể có lặp lại giá trị, thay đổi chi phiếu đến:

if(node.element >= MIN 
    && node.element <= MAX 
    && IsValidBST(node.left,MIN,node.element) 
    && IsValidBST(node.right,node.element,MAX)) 

Hoặc bạn sẽ nhận được kết quả không hợp lệ.

Answer 3

Ở đây MIN MAX chỉ định giá trị tối thiểu được lưu trữ trong cây và giá trị tối đa được lưu trữ trong cây.

I think simplest way to check the valid BST tree is traverse inorder and check if 
the values are in sorted order or not? if all the values are in sorted order that 
means its valid BST. 

Thực hiện http://justprogrammng.blogspot.com/2012/06/check-if-tree-is-bst-on-code-interview.html

Answer 4

Bạn nên gọi hàm như dưới đây. Trong đó INT_MIN và INT_MAX được xác định không đổi.

IsValidBST (root, INT_MIN, INT_MAX) 

Nhưng cách tiếp cận này sẽ không hoạt động đối với tất cả dữ liệu. Có nghĩa là, dữ liệu mà chúng tôi không biết giá trị MIN và MAX, như chuỗi hoặc bất kỳ loại người dùng tùy ý nào được xác định.

Để tìm hiểu xem liệu BT có phải là BST cho bất kỳ kiểu dữ liệu nào, bạn cần đi với cách tiếp cận dưới đây. 1. gọi hàm đệ quy cho đến cuối nút lá bằng cách sử dụng inorder traversal 2. Tự xây dựng các giá trị tối thiểu và giá trị tối đa của mình.

Miễn là phần tử cây phải nhỏ hơn/lớn hơn toán tử được xác định.

#define MIN (FirstVal, SecondVal) ((FirstVal) < (SecondVal)) ? (FirstVal):(SecondVal) 
#define MAX (FirstVal, SecondVal) ((FirstVal) > (SecondVal)) ? (FirstVal):(SecondVal) 

template <class T> 
bool IsValidBST (treeNode &root) 
{ 

    T min, max; 
    return IsValidBST (root, &min, &max); 
} 

template <class T> 
bool IsValidBST (treeNode *root, T *MIN , T *MAX) 
{ 
    T leftMin, leftMax, rightMin, rightMax; 
    bool isValidBST; 

    if (root->leftNode == NULL && root->rightNode == NULL) 
    { 
     *MIN = root->element; 
     *MAX = root->element; 
     return true; 
    } 

    isValidBST = IsValidBST (root->leftNode, &leftMin, &leftMax); 

    if (isValidBST) 
    isValidBST = IsValidBST (root->rightNode, &rightMin, &rightMax); 

    if (isValidBST) 
    { 
    *MIN = MIN (leftMIN, rightMIN); 
    *Max = MAX (rightMax, leftMax); 
    } 

    return isValidBST; 
}