二进制搜索树是一种特殊类型的二进制树，具有以下属性。

• 小于root的节点将在左子树中。
• 大于root的节点将是正确的子树。
• 它不应该有重复的节点
• 左和右子树也应该是二进制搜索树。

允许在二进制搜索树上执行以下操作

• 寻找
• 插入

搜索()

在二进制搜索中搜索节点非常简单。
根据要找到的值，我们只需遍历左(如果较小的)和右(如果更大)。

算法：

• 如果要找到的节点等于root，则搜索成功
• 如果要找到的节点小于root，则遍历左子树。
• 如果要找到的节点大于root，则遍历右子树
• 递归重复上述步骤，直到找到节点。

插入()

插入节点操作也很简单。
根据要插入的节点的值，我们只需将其与root和左(如果较小)或者右(如果更小)的左(如果较小)或者右(如果更大)。

算法：

• 将根节点作为当前节点
• 如果要插入节点<root
• 如果它已经离开了孩子，那就留下了左边
• 如果它没有左子，请插入节点
• 如果要插入节点> root
• 如果它有正确的孩子，遍历右
• 如果它没有右侧的子，请在此处插入节点。

完整的Java程序：

package org.arpit.theitroad.binarysearchtree;
 
public class BinarySearchTreeMain {
	public static class TreeNode
	{
		int data;
		TreeNode left;
		TreeNode right;
		TreeNode(int data)
		{
			this.data=data;
		}
	}
 
 
	public static boolean search(TreeNode root,TreeNode nodeToBeSearched)
	{
		if(root==null)
			return false;
		if(root.data== nodeToBeSearched.data)
		{
			return true;
		}
		boolean result=false;
 
		if(root.data > nodeToBeSearched.data)
			result=search(root.left,nodeToBeSearched);
		else if(root.data < nodeToBeSearched.data) 
			result= search(root.right,nodeToBeSearched); 
 
		return result; 
	} 
 
	public static TreeNode insert(TreeNode root,TreeNode nodeToBeInserted) 
	{ if(root==null) { 
		root=nodeToBeInserted; return root;
	} if(root.data > nodeToBeInserted.data)
	{
		if(root.left==null)
			root.left=nodeToBeInserted;
		else
			insert(root.left,nodeToBeInserted);
	}
	else if(root.data < nodeToBeInserted.data)
		if(root.right==null)
			root.right=nodeToBeInserted;
		else
			insert(root.right,nodeToBeInserted);
	return root;
	} 
 
	public static void inOrder(TreeNode root)
	{
		if(root==null)
			return;
		inOrder(root.left);
		System.out.print(root.data+" ");
		inOrder(root.right);
	}
	public static void main(String[] args)
	{
 
		//Creating a binary search tree
		TreeNode rootNode=createBinarySearchTree();
		TreeNode node55=new TreeNode(55);
		boolean result=search(rootNode,node55);
		System.out.println("Searching for node 55 : "+result);
		System.out.println("---------------------------");
		TreeNode node13=new TreeNode(13);
		TreeNode root=insert(rootNode,node13);
		System.out.println("Inorder traversal of binary tree after adding 13:");
		inOrder(root);
 
	} 
 
	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);
 
		insert(null,rootNode);
		insert(rootNode,node20);
		insert(rootNode,node10);
		insert(rootNode,node30);
		insert(rootNode,node60);
		insert(rootNode,node50);
		insert(rootNode,node70);
		insert(rootNode,node5);
		insert(rootNode,node55);
		return rootNode;
	}
 
}

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

Searching for node 55 : true
--------------------------
Inorder traversal of binary tree after adding 13:
5 10 13 20 30 40 50 55 60 70