二叉搜索树（二叉排序树）的定义：根节点比左子树的所有节点都大，比右节点的所有节点的值都小
插入有序节点，退化成单支树
1.查找效率最好O(logn)，最坏O(n)
2.插入效率和查找效率相同（只插入叶子节点）
3.删除效率最好O(logn)+O(1)->只有左子树或者右子树
最差O(logn)+O(logn)->左子树和右子树同时存在
将一个有序的数组，构建为一颗二叉搜索树
public class BinarySearchTree<T> {
TreeNode<T> root;
public BinarySearchTree(T[] arr){
root=createBinarySearchTree(arr,0,arr.length-1);
}
/**
*
* @param arr
* @param left
* @param right
* @return
*<p>Description:从有序的数组中构造一颗二叉搜索树 </p>
*/
public TreeNode<T> createBinarySearchTree(T[] arr,int left,int right){
if(left>right){
return null;
}
int mid=left+(right-left)/2;
//int mid=(left+right)/2;
TreeNode<T> root=new TreeNode(arr[mid]);
root.left=createBinarySearchTree(arr, left, mid-1);
root.right=createBinarySearchTree(arr, mid+1, right);
return root;
}
}
