二叉查找树（Binary Search Tree,BST），又称为二叉搜索树，二叉排序树，是一种对查找和排序都有用的特殊二叉树。
二叉查找树或是空树，或是满足如下性质的二叉树：
(资料图片)
1）若其左子树非空，则左子树 上所有结点的值均小于根结点的值；
2）若其右子树非空，则右子树上所有 结点的值均大于等于根结点的值；
3）其左右子树本省又各是一颗二叉查找树。
二叉查找树的特性：左子树 < 根 < 右子树，即二叉查找树的中序遍历是一个递增序列。
1.二叉查找树的查找
因为二叉查找树的中序遍历有序性，所以查找和二分查找类似，每次缩小查找范围，查找的效率较高。
算法步骤：
1）若二叉查找树为空，查找失败，返回空指针。
2）若二叉查找树非空，将待查找关键字x 与根节点的关键字 T-> data 比较：
若 x == T->data,查找成功，返回根结点指针；
若 x < T->data, 则递归查找左子树；
若 x > T-> data,则递归查找右子树。
算法实现：
BSTree SearchBST(BSTree T, ElemType key){ //二叉排序树的递归查找
if(! T || key == T->data)
return T;
else if (key < T->data)
return SearchBST(T->lchild, key);
else
return SearchBST(T->rchild,key);
}
2.二叉查找树的插入
因为二叉查找树的中序遍历有序性，首先要查找待插入关键字的插入位置，当查找不成功时，将待插入关键字作为新的叶子结点插入到最后一个查找结点的左孩子或右孩子。
算法步骤：
1）若二叉查找树为空，创建一个新的结点s,将待插入关键字放入新结点的数据域，s结点作为根结点，左右子树均为空；
2）若二叉查找树非空，将待查找关键字x 与根结点的关键字 T->data 比较：
若 x < T-> data,则将x 插入到左子树；
若 x > T-> data,则将x插入到右子树。
算法实现：
void InsertBST(BSTree &T, ElemType e){ //二叉排序树的插入
if(!T){
BSTree s = new BSTNode;
s->data = e;
s->lchild = s->rchild = NULL;
T = s;
}
else if(e < T-> data)
InsertBST(T->lchild,e);
else if(e > T-> data)
InsertBST(T ->rchild,e);
}
算法分析：
二叉查找树的插入需要先查找插入位置，插入本身只需要常数时间，但查找插入位置的时间复杂度为O(logn) 。
3.二叉查找树的创建
二叉查找树的创建可以从空数开始，按照输入关键字的顺序依次进行插入操作，最终得到一棵二叉树。
算法步骤:
1) 初始化二叉查找树为空树，T = NULL;
2) 输入一个关键字 x ,将x 插入到二叉查找树 T中；
3）重复步骤 2），直到关键字输入完毕。
算法实现：
void CreateBST(BSTree & T){
T = NULL;
ElemType e;
cin >> e;
while(e != ENDFLAG){ //ENGFALG为自定义常量，作为输入结束标志
InsertBST(T,e); //插入二叉排序树 T 中
cin >> e;
}
}
算法分析：
二叉查找树的创建，需要n次插入，每次需要O(logn)时间，因此创建二叉查找树的时间复杂度为O(nlogn)。相当于把一个无序序列转换为一个有序序列的排序过程。实质上，创建二叉查找树的过程和快速排序一样，根节点相当于快速排序中的基准元素，左右两部分划分的情况取决于基准元素，创建二叉查找树时，输入序列的次序不同，创建的二叉查找树是不同的。
4.二叉查找树的删除
首先要在二叉查找树中找到待删除的结点，然后执行删除操作。假设指针p指向待删除的结点，指针f指向p的双亲结点。根据待删除结点所在位置的不同，删除操作处理方法也不同，可分为三种情况：
（1）被删除结点左子树为空
如果被删除结点左子树为空，则令其右子树子承父业代替其位置即可。例如，在二叉树找树中删除P结点，如下图所示：
（2）被删除结点右子树为空
如果被删除结点右子树为空，则令其左子树子承父业代替其位置即可。
（3）被删除结点左右子树均不空
如果被删除结点的左子树和右子树均不空，则没办法再使用子承父业的方法了。根据二叉查找树的中序有序性，删除该结点时，可以用其直接前驱（或直接后继）代替其位置，让然后删除其直接前驱（或者直接后继）即可。那么中序遍历序列中，一个结点的直接前驱（或直接后继）是哪个结点呢？
直接前驱：中序遍历中，结点p 的直接前驱为其左子树的最右结点。即沿着p的左子树一直访问其右子树，直到没有右子树，就找到了最右结点。如图（a）所示，s指向p的直接前驱，q指向s的双亲。
直接后继：中序遍历中，结点p的直接后继为其右子树的最左结点。如图（b）所示。s指向p的直接后继，q指向s的双亲。
算法步骤：
1）在二叉查找树中查找待删除关键字的位置，p指向待 删除结点，f指向p的双亲结点，如果查找失败，则返回。
2）如果查找成功，则分三种情况进行删除操作：
*如果被删除结点左子树为空，则令其右子树子承父业代替其位置即可；
*如果被删除结点右子树为空，则令其左子树子承父业代替其位置即可；
*如果被删除结点右子树均不空，则令其直接前驱（或直接后驱）代替之，再删除其直接前驱（或直接后继）。
算法分析：
二叉查找树的删除，主要是查找的过程，需要O(logn)时间，删除的过程中，如果需要找被删结点的前驱，也需要O(logn)时间，二叉查找树的删除时间复杂度为O(logn)。
标签：
