二叉排序树
二叉排序树又称“二叉查找树”、“二叉搜索树”。
二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树：
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。
二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树可得到一个依据关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的时间复杂度等于树高，期望O(logn)，最坏O(n)。
虽然二叉排序树的最坏效率是O(n)，但它支持动态查找，且有很多改进版的二叉排序树可以使树高为O(logn)，如AVL、红黑树等。
二叉排序树的查找算法
在二叉排序树b中查找x的过程为：
1.若b是空树，则搜索失败，否则：
2.若x等于b的根节点的数据域之值，则查找成功；否则：
3.若x小于b的根节点的数据域之值，则搜索左子树；否则：
4.查找右子树。
二叉排序树的删除算法
在二叉排序树中删去一个结点，分三种情况讨论：
1.若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
2.若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。
3.若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整。比较好的做法是，找到*p的直接前驱（或直接后继）*s，用*s来替换结点*p，然后再删除结点*s。
typedef struct node{
int key;
struct node *lchild,*rchild;
}BSTree;
//二叉排序树的插入算法
int insertBST(BSTree* &p,int k){
if(p==NULL){
p = (BSTree*)malloc(sizeof(BSTree));
p->key = k;p->rchild=p->lchild=NULL;
return 1;
}
else if(k==p->key) return 0;
else if(k<p->key) return insertBST(p->lchild,k);
else return insertBST(p->rchild,k);
}
//二叉排序树的创建
BSTree *CreatBST(vector<int> &a,int n) // 返回树根指针
{ BSTree *bt=NULL; // 初始时bt 为空树
int i=0;
while (i<n)
{ insertBST(bt,a[i]); // 将a[i] 插入二叉排序树T中
i++;
}
return bt; // 返回建立的二叉排序树的根指针
}
//首先查找要删除节点是否在二叉排序树中
void delete_p(BSTree* &p);
int delete_k(BSTree* &root,int k){
if(root!=NULL){
if(k==root->key){
delete_p(root);
return 1;}
else if(k<root->key)
return delete_k(root->lchild,k);
else
return delete_k(root->rchild,k);
}
else
return 0;
}
void delete_both(BSTree* p,BSTree* &root)
{
BSTree* q;
if(root->rchild!=NULL)
delete_both(p,root->rchild); //找到直接前驱
else{
p->key = root->key; //值交换
q =root;root=root->lchild;
free(q);
}
}
//如果找到要删除的节点，进行删除
void delete_p(BSTree* & p){
BSTree *q;
//删除节点为叶子节点的情况，
if(p->lchild==NULL&&p->rchild==NULL)
free(p);
//删除节点只有右子树的情况，
else if(p->lchild==NULL){
q = p;
p = p->rchild;
free(q);
}
//删除节点只有左子树的情况，
if(p->rchild==NULL){
q = p;
p = p->lchild;
free(q);
}
//删除的节点有左右节点的情况
else delete_both(p,p->lchild);
}
void print(BSTree* &root){
if(root){
print(root->lchild);
cout << root->key <<" ";
print(root->rchild);
}
}
int main()
{
vector<int> data{ 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
int n = data.size();
//SI_sort(data,n);
//shell_sort(data,n);
//Bibble_sort(data,n);
//quickSort(data,0,n-1);
//select_sort(data,n);
//head_sort(data,n);
//merge_sort(data,n);
BSTree *root;
root = CreatBST(data,n);
print(root);
// for (int i = 0; i < n; i++)
// {
// cout << data[i]<<" ";
// }
return 0;
}