二叉查找树
也称为二叉搜索树或者二叉排序树,Binary Search Tree
１、每个结点都有一个作为查找依据的关键码(key)，所有结点的关键码互不相同。
２、左子树(如果存在)上所有结点的关键码都小于根结点的关键码。
３、右子树(如果存在)上所有结点的关键码都大于根结点的关键码。
４、左子树和右子树也是二叉查找树。
AVL, 红黑树，常用于计算机统计领域。
按中序遍历二叉搜索树，得到一个按关键码有序的序列。
下面是具体实现方法：
class BisortTree
{
public:
BisortTree(int a[], int n);
~ BiSortTree();
void InsertBST(BiNode<int> *root, BiNode<int> *s);
void DeleteBST(BiNode<int> *p, BiNode<int> *f);
BiNode<int> *SearchBST(BiNode<int> *root, int k);
private:
BiNode<int> *root;
};
template <class T>
struct BiNode{
T data;
BiNode<T> *lchild, *rchild;
}
/*插入算法*/
void BiSortTree::InsertBST(BiNode<int> *root, BiNode<int> *s)
{
if(root == NULL) root=s;
else if(s->data<root->data)InsertBST(root->lchild,s);
else InsertBST(root->rchild,s);
}
/* 二叉搜索树的构造函数算法 */
BiSortTree::BiSortTree(int r[],int n)
{
for (int i=0;i<n;i++)
{
s = new BiNode<int>; s->data=r[i];
s->lchild=s->rchild=NULL;
InsertBST(root,s);
}
}
void BiSortTree::DeleteBST(BiNode<int> *p, BiNode<int> *f)
{
if(!p->lchild &&!p->rchild){ //p 为叶子结点
f->lchild =NULL;
delete p;
}
else if(!p->rchild){ //p只有左孩子
f->lchild=p->lchild;
}
else if(!p->lchild){ //p只有右孩子
f->lchild=p->rchild;
delete p;
}
else { //左右子树均不为空
par=p;
s=p->rchild;
while(s->lchild!=NULL)
{
par=s;
s=s->lchild;
}
p->data = s->data;
if(par==p) par->rchild=s->rchild; //处理特殊情况
else par->lchild=s->rchild; //一般情况
delete s;
} //左右孩子都不为空处理完毕
}
/*二叉搜索树查找算法*/
BiNode * BiSortTree::SearchBST(BiNode<int> *root, int k)
{
if (root == NULL)return NULL;
else if(root->data ==k) return root;
else if(k<root->data) return SearchBST(root->lchild,k);
else return SearchBST(root->rchild,k);
}