二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

• 中文名 二叉排序树
• 外文名 Binary Sort Tree 
• 别 称 二叉查找树、二叉搜索树 
• 别称外文名 Binary Search Tree

基本步骤

　　若根结点的关键字值等于查找的关键字，成功。

　　否则，若小于根结点的关键字值，递归查左子树。

　　若大于根结点的关键字值，递归查右子树。

　　若子树为空，查找不成功。

　　插入算法：

　　首先执行查找算法，找出被插结点的父亲结点。

　　判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

　　若二叉树为空。则首先单独生成根结点。

　　注意：新插入的结点总是叶子结点。

　　void InsertBST(t，key)

　　//在二叉排序树中插入查找关键字key

　　{

　　if(t==NULL){

　　t=new BiTree;

　　t->lchild=t->rchild=NULL;

　　t->data=key;

　　return; }

　　if(keydata ) InsertBST(t->lchild,key);

　　else InsertBST (t->rchild, key );

　　}

　　void CreateBiTree(tree,d【 】,n）

　　//n个数据在数组d中，tree为二叉排序树根

　　{tree=NULL;

　　for(i=0;i InsertBST(tree,d);

　　}