导论：首先，沿着二分查找的思路，我们构造一种二叉树来查找，这种二叉树的左子树结点都小于根节点，右子树节点都大于根节点，这样一来，所有结点算是都排好序了，接下来就可以查找
基于二叉排序树的查找
一.二叉排序树的定义
所谓二叉排序树是一个什么样的东西，我们得弄清楚，以下是二叉排序树的定义：
1.若它的左子树非空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树非空，则右子树上所有结点的值都大于根节点的值
3.它的左子树和右子树也是一颗二叉排序树
有了定义，很多东西就都会显而易见了：
1.二叉排序树并不是一颗完全二叉树
2.和二叉判定树的对比：二叉判定树是一种特殊的二叉排序树，二叉判定树多了一个限定条件：左右子树的节点数目相差最多不能超过1个（小雨或等于1）
3.二叉排序树又名二叉查找树
好了，到这里给出二叉排序树的定义
typedef struct _TreeNode
{
struct _TreeNode *leftNode;
struct _TreeNode *rightNode;
TypeData data;
}TreeNode,*TreeRoot;
二.二叉排序树的插入
和堆的建立和维护类似，我们首先想解决的一个问题就是：已经有了一颗二叉排序树，怎样做到将一个值插入正确的位置，
给出二叉树的插入定义
TreeNode* Insert_Tree(TreeRoot &root,TypeData key)
{
if (!root)
{
TreeNode *node=new TreeNode;
node->data=key;
node->leftNode=nullptr;
node->rightNode=nullptr;
root=node;
return root;
}
else if (root->data==key)
{
return root;
}
else if (root->data<key)
{
return (Insert_Tree(root->rightNode,key));
}
else if (root->data>key)
{
return(Insert_Tree(root->leftNode,key));
}
}
这里是用递归实现的二叉排序树的插入，要注意以下几点：
递归开始返回的终结点有两个：
1.当根节点为null时
2.根节点的data值和key相等，这个时候就不需要插入了
插入完毕返回插入位置的结点
三.二叉排序树的建立
所谓二叉排序树的建立，也就是通过向一个空节点不断地插入结点来建立一颗二叉排序树，通过递归地插入，可得
void Create_Tree(TreeRoot& root)
{
TypeData key;
while (std::cin>>key)
{
Insert_Tree(root,key);
}
}
四.通过二叉排序树进行查找
这里，有两种方式，递归和非递归的
首先是递归的
TreeNode *find_InTree(TreeRoot root,TypeData key)
{
if (root)
{
if (root->data==key)
{
return root;
}
else if (root->data>key)
{
return find_InTree(root->leftNode,key);
}
else
{
return find_InTree(root->rightNode,key);
}
}
return nullptr;
}
然后是非递归的，用while循环代替递归达到递归的作用
TreeNode *find_InTree2(TreeRoot root,TypeData key)
{
TreeNode* p=root;
while (p)
{
if (p->data==key)
{
return p;
break;
}
else if (p->data>key)
{
p=p->leftNode;
}
else
{
p=p->rightNode;
}
}
return nullptr;
}
最后，简单地分析一下查找的时间复杂度吧！
二叉排序树的插入过程：很明显，二叉排序树过程最好情况是O(log2(n))，最差情况是O(n)，最差的情况时：二叉树变为一颗只有左子树或者只有右子树的二叉树，整个插入过程也退化成为顺序插入
二叉排序树的创建过程：很明显，假设有n个数，建立二叉排序树就要while循环n次插入过程，也就是说创建过程为O(nlog2(n))~O(n²)之间
二叉排序树的查找过程：很明显，基于二叉排序树的查找过程和二叉排序树的插入过程类似，时间复杂度也为O(log2(n))到O(n)之间
最后，程序执行过程使这样的：
排序二叉树的创建过程；
排序二叉树的查找过程；
这样看来，整个过程的时间复杂度为O(nlog2(n)到O(n²))之间，但是实际上表述的时候我们通常忽略创建过程，只考虑二叉树的查找过程，这样看来的话，整个过程的时间复杂度为O(log2(n))到O(n)之间