kiểm tra xem cây có phải là cây tìm kiếm nhị phân không

Question

Tôi đã viết mã sau đây để kiểm tra xem cây có phải là cây tìm kiếm nhị phân hay không. Vui lòng giúp tôi kiểm tra mã:

OK! Mã được chỉnh sửa ngay bây giờ. Giải pháp đơn giản này được đề xuất bởi một người nào đó trong các bài đăng dưới đây:

IsValidBST(root,-infinity,infinity); 

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; 
} 

Answer 1

Phương pháp chỉ nên thực hiện một việc tại một thời điểm. Ngoài ra cách bạn làm mọi thứ thường là Weird. Tôi sẽ cung cấp cho bạn một số mã giả gần như Java. Xin lỗi vì điều đó, nhưng tôi đã không chạm vào Java trong một thời gian. Tôi hy vọng nó sẽ giúp. Nhìn vào những bình luận tôi cũng đã làm trong câu hỏi và tôi hy vọng bạn sắp xếp nó ra!

Gọi isBST của bạn như thế:

public boolean isBst(BNode node) 
{ 
    return isBinarySearchTree(node , Integer.MIN_VALUE , Integer.MIN_VALUE); 
} 

Bên trong:

public boolean isBinarySearchTree(BNode node , int min , int max) 
{ 
    if(node.data < min || node.data > max) 
     return false; 
    //Check this node! 
    //This algorithm doesn't recurse with null Arguments. 
    //When a null is found the method returns true; 
    //Look and you will find out. 
    /* 
    * Checking for Left SubTree 
    */ 
    boolean leftIsBst = false; 
    //If the Left Node Exists 
    if(node.left != null) 
    { 
     //and the Left Data are Smaller than the Node Data 
     if(node.left.data < node.data) 
     { 
      //Check if the subtree is Valid as well 
      leftIsBst = isBinarySearchTree(node.left , min , node.data); 
     }else 
     { 
      //Else if the Left data are Bigger return false; 
      leftIsBst = false; 
     } 
    }else //if the Left Node Doesn't Exist return true; 
    { 
     leftIsBst = true; 
    } 

    /* 
    * Checking for Right SubTree - Similar Logic 
    */ 
    boolean rightIsBst = false; 
    //If the Right Node Exists 
    if(node.right != null) 
    { 
     //and the Right Data are Bigger (or Equal) than the Node Data 
     if(node.right.data >= node.data) 
     { 
      //Check if the subtree is Valid as well 
      rightIsBst = isBinarySearchTree(node.right , node.data+1 , max); 
     }else 
     { 
      //Else if the Right data are Smaller return false; 
      rightIsBst = false; 
     } 
    }else //if the Right Node Doesn't Exist return true; 
    { 
     rightIsBst = true; 
    } 

    //if both are true then this means that subtrees are BST too 
    return (leftIsBst && rightIsBst); 
} 

Bây giờ là: Nếu bạn muốn tìm Min và Max Giá trị của mỗi Subtree bạn nên sử dụng một container (Tôi đã sử dụng một ArrayList) và lưu trữ một bộ ba của Node, Min, Max đại diện cho nút gốc và các giá trị (rõ ràng).

ví dụ:

/* 
* A Class which is used when getting subTrees Values 
*/ 
class TreeValues 
{ 
    BNode root; //Which node those values apply for 
    int Min; 
    int Max; 
    TreeValues(BNode _node , _min , _max) 
    { 
     root = _node; 
     Min = _min; 
     Max = _max; 
    } 
} 

Và một:

/* 
* Use this as your container to store Min and Max of the whole 
*/ 
ArrayList<TreeValues> myValues = new ArrayList<TreeValues>; 

Bây giờ đây là một phương pháp mà tìm Min và Max giá trị của một nút cho trước:

/* 
* Method Used to get Values for one Subtree 
* Returns a TreeValues Object containing that (sub-)trees values 
*/ 
public TreeValues GetSubTreeValues(BNode node) 
{ 
    //Keep information on the data of the Subtree's Startnode 
    //We gonna need it later 
    BNode SubtreeRoot = node; 

    //The Min value of a BST Tree exists in the leftmost child 
    //and the Max in the RightMost child 

    int MinValue = 0; 

    //If there is not a Left Child 
    if(node.left == null) 
    { 
     //The Min Value is this node's data 
     MinValue = node.data; 
    }else 
    { 
     //Get me the Leftmost Child 
     while(node.left != null) 
     { 
      node = node.left; 
     } 
     MinValue = node.data; 
    } 
    //Reset the node to original value 
    node = SubtreeRoot; //Edit - fix 
    //Similarly for the Right Child. 
    if(node.right == null) 
    { 
     MaxValue = node.data; 
    }else 
    { 
     int MaxValue = 0; 
     //Similarly 
     while(node.right != null) 
     { 
      node = node.right; 
     } 
     MaxValue = node.data; 
    } 
    //Return the info. 
    return new TreeValues(SubtreeRoot , MinValue , MaxValue); 
} 

Nhưng điều này trả về giá trị cho một Node chỉ, Vì vậy, chúng tôi sẽ sử dụng điều này để tìm Cây nguyên thủy:

public void GetTreeValues(BNode node) 
{ 
    //Add this node to the Container with Tree Data 
    myValues.add(GetSubTreeValues(node)); 

    //Get Left Child Values, if it exists ... 
    if(node.left != null) 
     GetTreeValues(node.left); 
    //Similarly. 
    if(node.right != null) 
     GetTreeValues(node.right); 
    //Nothing is returned, we put everything to the myValues container 
    return; 
} 

Sử dụng phương pháp này, cuộc gọi của bạn sẽ trông như thế

if(isBinarySearchTree(root)) 
    GetTreeValues(root); 
//else ... Do Something 

này là gần như Java. Nó sẽ làm việc với một số sửa đổi và sửa chữa. Tìm một cuốn sách OO tốt, nó sẽ giúp bạn. Lưu ý rằng giải pháp này có thể được chia nhỏ thành nhiều phương pháp hơn.

Answer 2

Thực sự không có ý nghĩa gì khi trả về INTEGER.MIN, INTEGER.MAX làm giá trị cho một cây trống. Có lẽ sử dụng một số nguyên và trả về null thay vào đó.

Answer 3

đúng, một giải pháp đơn giản là làm một chuyến viếng thăm inorder

java code here

Answer 4

boolean isBST(TreeNode root, int max, int min) { 
     if (root == null) { 
      return true; 
     } else if (root.val >= max || root.val <= min) { 
      return false; 
     } else { 
      return isBST(root.left, root.val, min) && isBST(root.right, max, root.val); 
     } 

    } 

một cách khác giải quyết vấn đề này .. tương tự với mã của bạn

Answer 5

public void inorder() 
    { 
     min=min(root); 
     //System.out.println(min); 
     inorder(root); 

    } 

    private int min(BSTNode r) 
     { 

      while (r.left != null) 
      { 
       r=r.left; 
      } 
      return r.data; 


    } 


    private void inorder(BSTNode r) 
    { 

     if (r != null) 
     { 
      inorder(r.getLeft()); 
      System.out.println(r.getData()); 
      if(min<=r.getData()) 
      { 
       System.out.println(min+"<="+r.getData()); 
       min=r.getData(); 
      } 
      else 
      System.out.println("nananan"); 
      //System.out.print(r.getData() +" "); 
      inorder(r.getRight()); 
      return; 
     } 
    } 

Answer 6

boolean bst = isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); 

public boolean isBST(Node root, int min, int max) { 
    if(root == null) 
     return true; 

    return (root.data > min && 
      root.data < max && 
      isBST(root.left, min, root.data) && 
      isBST(root.right, root.data, max)); 
    } 

Answer 7

CẬP NHẬT : Tôi chỉ thấy rằng điều này solu tion đã được đề xuất trước đó.Xin lỗi về những người này, có thể ai đó vẫn thấy phiên bản của tôi hữu ích

Đây là giải pháp sử dụng In-Order Traversal để kiểm tra thuộc tính BST. Trước khi tôi cung cấp giải pháp, tôi đang sử dụng định nghĩa về BST không cho phép trùng lặp. Điều này có nghĩa là mỗi giá trị trong BST là duy nhất (đây chỉ là để đơn giản).

Mã cho đệ quy inorder in:

void printInorder(Node root) { 
    if(root == null) {     // base case 
     return; 
    } 
    printInorder(root.left);   // go left 
    System.out.print(root.data + " "); // process (print) data 
    printInorder(root.right);   // go right 
} 

Sau traversal inorder này trên một BST, tất cả các dữ liệu sẽ được in theo thứ tự tăng dần được sắp xếp. Ví dụ cây:

5 
3 7 
1 2 6 9 

sẽ phải inorder in:

1 2 3 5 6 7 9 

Bây giờ, thay vì in nút, chúng ta có thể theo dõi các giá trị trước đó trong chuỗi In-Trình tự, so sánh nó với giá trị của nút hiện tại. Nếu giá trị của nút hiện tại nhỏ hơn giá trị trước đó, điều này có nghĩa là chuỗi không nằm trong thứ tự sắp xếp tăng dần và thuộc tính BST bị vi phạm.

Ví dụ, cây:

5 
3 7 
1 8 6 9 

Có một sự vi phạm. Con phải của là và điều này sẽ ổn nếu là nút gốc. Tuy nhiên, trong BST sẽ kết thúc dưới dạng con trái của và không phải là con phải của . Do đó, cây này không phải là BST. Vì vậy, các mã mà làm theo ý tưởng này:

/* wrapper that keeps track of the previous value */ 
class PrevWrapper { 
    int data = Integer.MIN_VALUE; 
} 

boolean isBST(Node root, PrevWrapper prev) { 
    /* base case: we reached null*/ 
    if (root == null) { 
     return true; 
    } 

    if(!isBST(root.left, prev)) { 
     return false; 
    } 
    /* If previous in-order node's data is larger than 
    * current node's data, BST property is violated */ 
    if (prev.data > root.data) { 
     return false; 
    } 

    /* set the previous in-order data to the current node's data*/ 
    prev.data = root.data; 

    return isBST(root.right, prev); 
} 

boolean isBST(Node root) { 
    return isBST(root, new PrevWrapper()); 
} 

Các trong trật tự traversal cho cây mẫu sẽ không kiểm tra cho nút từ trước trong trật tự của là , mà lớn hơn nên thuộc tính BST bị vi phạm.

Answer 8

Cây tìm kiếm nhị phân có các thuộc tính sau trong đó khóa cho nút bên trái phải là < = khóa nút gốc và phím nút phải phải lớn hơn gốc. Vì vậy, vấn đề chúng tôi gặp phải là nếu các phím trong cây không phải là duy nhất và một quá trình truyền tải trật tự đã được thực hiện, chúng tôi có thể có được một tình huống hai lần theo thứ tự sản xuất cùng một chuỗi, trong đó 1 sẽ là bst hợp lệ và khác sẽ không, điều này sẽ xảy ra nếu chúng ta có một cây nơi nút trái = root (bst hợp lệ) và nút phải = root (không hợp lệ không phải là bst). Để thực hiện việc này, chúng tôi cần duy trì một khoảng thời gian tối thiểu/tối đa hợp lệ mà khóa 'được truy cập' phải nằm giữa và chúng tôi chuyển phạm vi này khi chúng tôi sử dụng lại các nút khác.

#include <limits> 

int min = numeric_limits<int>::min(); 
int max = numeric_limits<int>::max(); 

The calling function will pass the above min and max values initially to isBst(...) 

bool isBst(node* root, int min, int max) 
{ 
    //base case 
    if(root == NULL) 
     return true; 

    if(root->val <= max && root->val >= min) 
    { 
     bool b1 = isBst(root->left, min, root->val); 
     bool b2 = isBst(root->right, root->val, max); 
     if(!b1 || !b2) 
      return false; 
     return true; 
    } 
    return false; 
} 

Answer 9

Chúng tôi thực hiện bước đầu tiên theo chiều sâu qua cây, kiểm tra từng nút để có hiệu lực khi chúng tôi đi. Một nút cho trước là hợp lệ nếu nó lớn hơn tất cả các nút tổ tiên, nó nằm trong cây con bên phải và ít hơn tất cả các nút tổ tiên, nó nằm trong nhánh trái của.Thay vì theo dõi từng tổ tiên để kiểm tra sự bất bình đẳng này, chúng ta chỉ cần kiểm tra số lớn nhất nó phải lớn hơn (số dưới của nó) và số nhỏ nhất nó phải nhỏ hơn (upperBound của nó).

import java.util.Stack; 

final int MIN_INT = Integer.MIN_VALUE; 
final int MAX_INT = Integer.MAX_VALUE; 

public class NodeBounds { 

BinaryTreeNode node; 
int lowerBound; 
int upperBound; 

public NodeBounds(BinaryTreeNode node, int lowerBound, int upperBound) { 
    this.node = node; 
    this.lowerBound = lowerBound; 
    this.upperBound = upperBound; 
} 
} 

public boolean bstChecker(BinaryTreeNode root) { 

// start at the root, with an arbitrarily low lower bound 
// and an arbitrarily high upper bound 
Stack<NodeBounds> stack = new Stack<NodeBounds>(); 
stack.push(new NodeBounds(root, MIN_INT, MAX_INT)); 

// depth-first traversal 
while (!stack.empty()) { 
    NodeBounds nb = stack.pop(); 
    BinaryTreeNode node = nb.node; 
    int lowerBound = nb.lowerBound; 
    int upperBound = nb.upperBound; 

    // if this node is invalid, we return false right away 
    if ((node.value < lowerBound) || (node.value > upperBound)) { 
     return false; 
    } 

    if (node.left != null) { 
     // this node must be less than the current node 
     stack.push(new NodeBounds(node.left, lowerBound, node.value)); 
    } 
    if (node.right != null) { 
     // this node must be greater than the current node 
     stack.push(new NodeBounds(node.right, node.value, upperBound)); 
    } 
} 

// if none of the nodes were invalid, return true 
// (at this point we have checked all nodes) 
return true; 
}