前面总结了顺序查找，二分查找，分块查找算法，此篇博文将详解介绍二叉排序算法（Binary Sort Tree）。
在介绍二叉排序算法之前，首先介绍什么事二叉排序树（BST）。
首先从二叉树讲起：
1、二叉树的概念
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 +1。
二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：
//二叉树结点 typedef struct BiTNode{//数据char data;//左右孩子指针struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
2、二叉树的建立
通过读入一个字符串，建立二叉树的算法如下：//按先序序列创建二叉树 int CreateBiTree(BiTree &T){char data;//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树scanf("%c",&data);if(data == '#'){T = NULL;}else{T = (BiTree)malloc(sizeof(BiTNode));//生成根结点T->data = data;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);}return 0; }
3、二叉树的遍历
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
先序遍历：访问根节点，访问左子节点，访问右子节点
中序遍历：访问左子结点，访问根节点，访问右子节点
后序遍历：访问左子节点，访问右子节点，访问根节点
层次遍历：从顶层到底层，按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。
事实上，知道任意两种方式，并不能唯一地确定树的结构，但是，只要知道中序遍历和另外任意一种遍历方式，就一定可以唯一地确定一棵树。
// 先序遍历void preOrderTraverse(BST T){if(T){cout << T->key <<" ";preOrderTraverse(T->lChild);preOrderTraverse(T->rChild);}}// 中序遍历void inOrderTraverse(BST T){if(T){inOrderTraverse(T->lChild);cout << T->key <<" ";inOrderTraverse(T->rChild);}}//后序遍历void postOrderTraverse(BST T){if(T){postOrderTraverse(T->lChild);postOrderTraverse(T->rChild);cout << T->key <<" ";}}//层次遍历void LevelOrder(BST T){BST p = T;//队列queue<BST> queue;queue.push(p);while(!queue.empty()){p = queue.front();cout<< p->key<<" ";queue.pop();if(p->lChild != NULL)queue.push(p->lChild);if(p->rChild != NULL)queue.push(p->rChild);}}
4.BST树的概念
它或者是一棵空树；或者是具有下列性质的二叉树：
(1)若左子树不空，则左子树上所有结点的值均小于左子树所在树的根结点的值；
(2)若右子树不空，则右子树上所有结点的值均大于右子树所在树的根结点的值；
(3)左、右子树也分别为二叉排序树；
最大关键字及最小关键字元素：顾名思义，肯定是二叉搜索树的最大最小值，以最大关键字为例，一直查询树的右孩子，直到该节点无右孩子为止，该节点就是最大关键字， 当然，最小关键字同理；
后继与前驱：对一个节点来说，最大的小于该节点值的即是前驱，最小的大于该节点 值的即是后继。以后继为例，如果该节点的右子树不为空，那么后继就是右子树中最小关键字元素；若是该节点右孩子不存在，这时，只需由该节点往上寻找，直到这个节点是其 父节点的左孩子即可。当然，前驱也是类似情况；
5、BST树的查找：
时间复杂度与树的深度的有关，O(log n)。
步骤：若根结点的关键字值等于查找的关键字，成功。
否则：若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
6、BST树的插入
首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左儿子还是右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
注意：新插入的结点总是叶子结点，所以算法复杂度是O(h)。
BST树的建立过程就是依次插入的过程。
7、BST树的删除
如果删除的结点没有孩子，则删除后算法结束；
如果删除的结点只有一个孩子，则删除后该孩子取代被删除结点的位置；
华贵的衣服穿在心肠污浊的人身上，显得更丑恶。
