二叉排序树：又称二叉查找树（BST，Binary Search Tree）
二叉排序树的性质：左子树节点值 < 根节点值 < 右子树节点值
所以 对一棵二叉排序树进行中序遍历，会得到一个递增的序列
定义二叉排序树的结点
//二叉排序树的结点
typedef struct BSTNode{int key;struct BSTNode *lchild ,*rchild;
}BSTNode,*BSTree;二叉排序树的非递归查找值为Key的结点 最坏空间复杂度为 O（1）
//在二叉树中查找值为Key的结点
BSTNode *BST_Search(BSTree T,int key){while(T!=NULL&&key!=T->key){ //如果树空或者等于根节点值，就结束循环if(key<T->key) T=T->lchild; //小于，则在左子树上查找else T=T->rchild; //大于，则在右子树上进行查找}return T;
}二叉排序树的递归实现查找值为Key的结点 最坏空间复杂度为O（H）H 取决与二叉排序树的高度
//在二叉排序树中查找值为Key的结点，（递归实现）
BSTNode *BSTSearch(BSTree T,int key){if(T==NULL)return NULL; //查找失败if(key==T->key)return T; //查找成功else if(key<T->key)return BSTSearch(T->lchild,key); //在左子树中找else return BSTSearch(T->rchild,key); //在右子树中找
}二叉排序树的插入（递归方式实现）
注意：传入的参数需要使用 引用 而且每次插入的结点都是叶子结点
//在二叉排序树中插入关键字为K的结点（递归实现）int BST_Insert(BSTree &T,int k){ //注意：传入的参数需要使用引用类型，因为需要返回改变之后的根节点的值if(T==NULL){ //原树为空，新插入的节点为根节点T=(BSTree)malloc(sizeof(BSTNode));T->key=k;T->lchild=T->rchild=NULL;return 1; //返回1，插入成功}else if(k==T->key) //树中存在相同关键字的结点，不进行插入，插入失败，因为二叉排序树中不允许有相同元素的存在return 0;else if(k<T->key) //插入到T的左子树return BST_Insert(T->lchild,k);else //插入到T的右子树return BST_Insert(T->rchild,k);
}二叉树的插入操作（使用非递归实现）
二叉树的构造（就是一个不断插入新节点的过程）
//按照 str[] 中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){T=NULL; //初始时T为空树int i=0;while(i<n){ //依次将每个关键字插入到二叉排序树中BST_Insert(T,str[i]);i++;}
}不同的关键字序列可能得到同款二叉树，也可能得到不同款的二叉排序树
二叉排序树的删除
1 要删除的结点是叶节点的情况，则直接进行删除，并不会破坏二叉排序树的性质
2 要删除的结点只有左子树或者只有右子树时，直接让子树替代被删除结点的位置
3 要删除的结点既有左子树，也有右子树的情况时，让被删除结点的 中序 遍历的后继结点替换被删除结点的位置。其中序遍历的后续节点的右子树中最左下结点（该节点一定没有左子树，让被替换结点的右子树直接替代它原来的位置就行）
具体过程可以见下图
或者使用被删除结点的直接前驱替代被删除的结点（即左子树中最右下的结点）
二叉排序树的查找效率的分析（一般使用平均查找长度进行评估）
查找效率取决与树的高度