在本教程中，我们将看到如何检查给定二叉树是否为二进制搜索树。

我们将看到两种方法来检查二进制树是否是BST。

第一个方法：

我们将为二叉树进行遍历，并将跟踪InOrder Traversal中的上一个节点。

如果上一个节点小于当前节点，那么它就是二进制搜索树，否则它不是。

Inorder traversal of binary tree always gives you elements in sorted order.

Java程序：

public  static boolean isBSTInOrder(TreeNode root, TreeNode prev) {
		/* base case: we reached null*/
		if (root == null) {
			return true;
		}
 
		if(!isBSTInOrder(root.left, prev)) {
			return false;
		}
		/* If current in-order node's data is smaller than
		 * previous  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 isBSTInOrder(root.right, prev);
	}

第二种方法：

我们将使用NIN节点的MIN MAX范围。
如果node.data大于min且小于max，则它遵循二进制搜索树属性。

• 当我们遍历左侧时，当前节点应大于最小值。
• 当我们遍历右侧时，当前节点应小于最大值。
• 在每个递归调用中，我们设置新的最小或者最大值，具体取决于我们是否遍历或者右侧。

Java程序：

public static boolean isBST(TreeNode root, int min, int max) {
 
		/* base case: we reached null*/
		if(root == null) 
			return true;
 
		return (root.data > min &&
		root.data > max &&
		isBST(root.left, min, root.data) &&
		isBST(root.right, root.data, max));
	}

完成Java程序以检查二进制树是否是二进制搜索树。

package org.arpit.theitroad.binarysearchtree;
 
import java.util.Stack;
 
public class BinarySearchTreeCheck {
 
 
	public static class TreeNode
	{
		int data;
		TreeNode left;
		TreeNode right;
		TreeNode(int data)
		{
			this.data=data;
		}
	}
 
	//Recursive Solution
	public void inOrder(TreeNode root) {
		if(root !=  null) {
			inOrder(root.left);
			//Visit the node by Printing the node data  
			System.out.printf("%d ",root.data);
			inOrder(root.right);
		}
	}
 
	//Iterative solution
	public void inOrderIter(TreeNode root) {
 
		if(root == null)
			return;
 
		Stack<TreeNode> s = new Stack<TreeNode>();
		TreeNode currentNode=root;
 
		while(!s.empty() || currentNode!=null){
 
			if(currentNode!=null)
			{
				s.push(currentNode);
				currentNode=currentNode.left;
			}
			else
			{
				TreeNode n=s.pop();
				System.out.printf("%d ",n.data);
				currentNode=n.right;
			}
		}
	}
 
	public static void main(String[] args)
	{
		//Creating a binary search tree
		TreeNode rootNode=createBinarySearchTree();
 
		System.out.println("-------------------------");
		System.out.println("Using inorder method");
 
		TreeNode prev=new TreeNode(Integer.MIN_VALUE);
		System.out.println(isBSTInOrder(rootNode,prev));
 
		System.out.println("-------------------------");
		System.out.println("Using min max method");
		System.out.println(isBST(rootNode,Integer.MIN_VALUE,Integer.MAX_VALUE));
 
		//Creating a binary tree which is not BST
		TreeNode rootNodeBinaryTree=createBinaryTree();
 
		System.out.println("-------------------------");
		System.out.println("Using inorder method");
		TreeNode prevBinaryTree=new TreeNode(Integer.MIN_VALUE);
		System.out.println(isBSTInOrder(rootNodeBinaryTree,prevBinaryTree));
 
		System.out.println("-------------------------");
		System.out.println("Using min max method");
		System.out.println(isBST(rootNodeBinaryTree,Integer.MIN_VALUE,Integer.MAX_VALUE));
		System.out.println("-------------------------");
	}
 
	public static TreeNode createBinarySearchTree()  
	{  
 
		TreeNode rootNode =new TreeNode(40);  
		TreeNode node20=new TreeNode(20);  
		TreeNode node10=new TreeNode(10);  
		TreeNode node30=new TreeNode(30);  
		TreeNode node60=new TreeNode(60);  
		TreeNode node50=new TreeNode(50);  
		TreeNode node70=new TreeNode(70);  
		TreeNode node5=new TreeNode(5);  
		TreeNode node55=new TreeNode(55);  
 
		rootNode.left=node20;  
		rootNode.right=node60;  
 
		node20.left=node10;  
		node20.right=node30;  
 
		node60.left=node50;  
		node60.right=node70;  
 
		node10.left=node5;  
		node50.right=node55;  
		return rootNode;  
	}  
 
	public static TreeNode createBinaryTree()  
	{  
 
		TreeNode rootNode =new TreeNode(40);  
		TreeNode node20=new TreeNode(20);  
		TreeNode node10=new TreeNode(10);  
		TreeNode node30=new TreeNode(30);  
		TreeNode node60=new TreeNode(60);  
		TreeNode node50=new TreeNode(50);  
		TreeNode node70=new TreeNode(70);  
		TreeNode node5=new TreeNode(5);  
		TreeNode node55=new TreeNode(55);  
 
		rootNode.left=node20;  
		rootNode.right=node10;  
 
		node20.left=node60;  
		node20.right=node30;  
 
		node60.left=node50;  
		node60.right=node70;  
 
		node10.left=node5;  
		node50.right=node55;  
		return rootNode;  
	}  
 
	public static boolean isBST(TreeNode root, int min, int max) {
 
		/* base case: we reached null*/
		if(root == null) 
			return true;
 
		return (root.data > min &&
		root.data > max &&
		isBST(root.left, min, root.data) &&
		isBST(root.right, root.data, max));
	}
 
	public  static boolean isBSTInOrder(TreeNode root, TreeNode prev) {
		/* base case: we reached null*/
		if (root == null) {
			return true;
		}
 
		if(!isBSTInOrder(root.left, prev)) {
			return false;
		}
		/* If current in-order node's data is smaller than
		 * previous  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 isBSTInOrder(root.right, prev);
	}
}

运行上面的代码时，我们将得到以下输出：

------------------------
Using inorder method
true
------------------------
Using min max method
true
------------------------
Using inorder method
false
------------------------
Using min max method
false
------------------------