二叉排序树
二叉排序树（Binary Search Tree）又叫二叉查找树。要么是一棵空树，要么是一颗具有下列特性的二叉树：
- 如果左子树不为空，那么左子树上所有结点关键字值都小于根节点。
- 如果右子树不为空，那么右子树上所有结点关键字值都大于根节点。
- 左右子树分别是一颗BST。
也就是说，BST的中序遍历一定是升序。
BST构造和插入
#include <iostream>
using namespace std;
// BST的结点
typedef struct node
{
int key;
struct node *lChild, *rChild;
}Node, *BST;
// 在给定的BST中插入结点，其数据域为element, 使之称为新的BST
bool BSTInsert(Node * &p, int element)
{
if(NULL == p) // 空树
{
p = new Node;
p->key = element;
p->lChild = p->rChild = NULL;
return true;
}
if(element == p->key) // BST中不能有相等的值
return false;
if(element < p->key) // 递归
return BSTInsert(p->lChild, element);
return BSTInsert(p->rChild, element); // 递归
}
// 建立BST
void createBST(Node * &T, int a[], int n)
{
T = NULL;
int i;
for(i = 0; i < n; i++)
{
BSTInsert(T, a[i]);
}
}
// 先序遍历
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);
}
}
int main()
{
int a[10] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8};
int n = 10;
BST T;
// 并非所有的a[]都能构造出BST,所以，最好对createBST的返回值进行判断
createBST(T, a, n);
preOrderTraverse(T);
cout << endl;
inOrderTraverse(T);
cout << endl;
return 0;
}
BST的查找
BST BST_Search(BST root,int key)
{
while(root != NULL && root->key != key)
{
if(key < root->key)
root = root->lchild;
else
root = root->rchild;
}
return root;
}
BST的删除
BST的删除操作有三种情况：
- 如果被删除结点是叶子结点，可以直接删除，不会破坏BST的性质。
- 如果被删除结点z只有一颗左子树或一颗右子树，则让z的子树成为z父节点的子树，代替z的位置。
- 如果被删除结点z有两颗子树，则令z的直接后继（或直接前驱）代替z，然后从BST中删去这个直接后继（或直接前驱），这样就转换成第一或第二种情况。
例1：删除数据为16的节点，是叶子节点，可以直接删除
例2：删除数据为25的节点，它下面有唯一一个子节点35, 上移到替换之
例3：删除节点数据为5的节点，找到被删除节点右子树的最小节点（或者左子树最大结点）。需要一个临时变量successor，将11节点下面的子节点进行查询，找到右子树最小节点7，并把右子树最小节点7替换被删除节点，维持二叉树结构（8是后插进来的）。如下图
BST的查找效率分析
对于高度为h的BST，插入和删除的时间复杂度都是O(h)。但是在最坏的情况下，即构造的BST输入序列是有序的，则会形成一个倾斜的单支树，此时BST的性能显著变坏，树的高度也增加为元素个数N。
由上可知，BST查找算法的平均查找长度主要取决于树的高度。
- 若二叉树是一个只有左子树或右子树的单支树，平均查找长度和单链表相同，为O(n)；
- 若树中每个结点左右子树高度大致相同时，树高为logN。则平均查找长度与logN成正比，查找的平均时间复杂度在O(logN)数量级上。