判断一棵树是否是二叉搜索树

1.什么是二叉搜索树？
二叉搜索树：如果一棵树为空树，那么是二叉搜索树；如果左子树的所有节点都小于根节点，右子树所有节点都大于根节点，那么是二叉搜索树
2.那么怎么编码呢？
根据BST的定义，我们往往想到使用递归来判断，那么会写出下面的代码，这样是错误的，因为仅能保证：左孩子<根<右孩子，不能保证左子树<根<右子树

	public static  boolean is_BST(Node head)
	{
		if(head==null)
			return true;
		if(head.left!=null&&head.left.value>head.value)
			return false;
		if(head.right!=null&&head.right.value<head.value)
			return false;
		if(!is_BST(head.left)||!is_BST(head.right))
			return true;
		else
			return false;
	}

3.那么怎样改进呢？
保证每次判断的节点都大于左子树最大，小于右子树的最小即可

//获取最大值
    public static int max_value(Node head)
	{
		if(head==null)
			return Integer.MAX_VALUE;
		while(head.right!=null)
			head=head.right;
		return head.value;
	}
	//获取最小值
	public static int min_value(Node head)
	{
		if(head==null)
			return Integer.MIN_VALUE;
		while(head.left!=null)
			head=head.left;
		return head.value;
	}
	
	public static boolean is_bst(Node head)
	{
		if(head==null)
			return true;
		//根节点小于左子树最大值，判错
		if(head.left!=null&&max_value(head.left)>head.value)
			return false;
		//根节点大于左子树最小值，判错
		if(head.right!=null&&min_value(head.right)<head.value)
			return false;
		
		if(!is_BST(head.left)||!is_BST(head.right))
			return true;
		else
			return false;
	}

3.非递归版本
二叉搜索树是中序有序的，因为左子树<根<右子树

public static boolean is_Bst(Node head)
	{
		Stack<Node> stack= new Stack<Node>();
		Vector<Integer> arr=new Vector<Integer>();
		Node point=head;
		while(!stack.isEmpty()||point!=null)
		{
			while(point!=null)
			{
				stack.push(point);
				point=point.left;
			}
			if(!stack.isEmpty())
			{
				point=stack.pop();
				arr.add(point.value);
				point=point.right;
			}	
		}
		for(int i=1;i<arr.size();i++)
			if(arr.get(i-1)>arr.get(i))
				return false;
		return true;
	}