二叉搜索树的根插入、选择、删除、合并、排序等操作的实现

标签：–fonts技术freeseapoperrotl逆时针

源码例如以下：

这里的Key 不当为keyword对待。 而是把Item.c作为keyword对待

#include <stdlib.h>
#include <stdio.h>
//#define Key int
typedef int Key;
struct Item{
Key key;
char c;
};
typedef struct STnode* link;
struct STnode{
Item item ; link l,r; int N;
};

static link head , z ;
static struct Item NULLitem ;

Key key(Item item){
return item.key;
}
//创建一个节点
link NEW(Item item, link l,link r, int N){
link x = (link)malloc(sizeof *x);
x->item = item;x->l = l;x->r = r;x->N = N;
if(head==z)head=x; //这句话不能少！！！
return x;
}
//初始化
void STinit(){
head = ( z = NEW(NULLitem,0,0,0));
}
//节点个数
int STcount(){
return head->N;
}
//搜索子程序
Item searchR(link h, char v){
char t = h->item.c;
if(h==z)return NULLitem;
if(v==t) return h->item;
if(v<t) return searchR(h->l,v);
else return searchR(h->r,v);
}
//搜索主程序
Item STsearch(Key v){
return searchR(head,v);
}

//选择第K小关键值的项 K从0開始
Item selectR(link h, int k) {
int t;
if(h==z)return NULLitem;
t = (h->l==z)?0:h->l->N;
if(t>k) return selectR(h->l,k);
if(t<k) return selectR(h->r,k-t-1);
return h->item;
}

Item STselect(int k){
return selectR(head,k);
}

//—————-根插入——————–//
//右旋转 顺时针旋转
link rotR(link h){
link x = h->l; h->l = x->r; x->r=h;
}
//左旋转 逆时针旋转
link rotL(link h){
link x = h->r; h->r = x->l; x->l=h;
}

//插入子程序
link insertT(link h, Item item){
// Key v = key(item), t = key(h->item);
char v = item.c, t = h->item.c;
if(h==z)return NEW(item,z,z,1);
if(v<t) {h->l = insertT(h->l,item); h = rotR(h); }
else {h->r = insertT(h->r,item); h = rotL(h);}
(h->N)++;return h;
}
//BST根插入主程序
void STinsert(Item item){ //新插入的节点都会当作根节点
head = insertT(head,item);
}

//—————-根插入——————–//

//—————-删除一个节点—-方法1—–乾坤大挪移———–//

link partR(link h, int k) {
int t = h->l->N; //为什么没有推断非空？
if(t>k){h->l = partR(h->l,k);h=rotR(h);}
if(t<k){h->r = partR(h->r,k-t-1);h=rotL(h);}
return h;
}
link joinLR(link a ,link b){
if(b==z)return a;
b=partR(b,0);
b->l = a;
return b;
}

link delR(link h, char k){
link x; char t = h->item.c;

if(h==z)return z;
if(t>k)h->l=delR(h->l,k);
if(t<k)h->r=delR(h->r,k);
if(t==k){
x = h;h=joinLR(h->l,h->r);free(x);
}
return h;
}
//删除主程序
void STdelete(char v){
head = delR(head,v);
}
//—————-删除一个节点—–方法1—–乾坤大挪移———-//

//—————-删除一个节点—–方法2—————//
//删除子程序
Item deleteR(link F){
Item tmp; link p;
if(F->l==NULL){
p = F;
tmp = F->item;
F = F->r;
free(p);
return tmp;
}else return deleteR(F->l);
}
//删除子程序
void deleteRR(link h , Key v){

if(h!=NULL){
Key t = key(h->item);
if(v<t) deleteRR(h->l,v);
else if(v>t) deleteRR(h->r,v);
else
if(h->l==NULL) { //处理仅仅有一颗子树或没有子树的情况 1
link p = h->r; h=p; free(p);
}
else if(h->r==NULL){ //处理仅仅有一颗子树或没有子树的情况 2
link p = h->l; h=p; free(p);
}
else h->item= deleteR(h->r); //假设待删除的节点既有左子树又有右子树
//则用该节点右子树的最左下节点替换之，维持二叉搜索树
}
}
//删除主程序
void STdelete2(Key v){
deleteRR(head,v);
}
//—————-删除一个节点—–方法2—————//

void sortR(link h){
if(h==z)return;
sortR(h->l);
if(h->item.key!=0)
printf(\”%c \”,h->item.c);
sortR(h->r);
}
//二叉搜索树排序
void STsort(link h){
sortR(h);
}
//接连两颗二叉搜索树
link STjoin(link a ,link b){
if(b==z)return a;
if(a==z)return b;
b = insertT(b,a->item);
b->l = STjoin(a->l,b->l);
b->r=STjoin(a->r,b->r);
free(a);
return b;
}

void test(){
struct Item item1 = {322,‘a‘};
struct Item item2 = {23,‘s‘};
struct Item item3 = {2,‘e‘};
struct Item item4 = {332,‘r‘};
struct Item item5 = {332,‘c‘};
struct Item item6 = {332,‘h‘};
struct Item item7 = {112,‘i‘};
STinit();
STinsert(item1);STinsert(item2);
STinsert(item3);STinsert(item4);
STinsert(item5);STinsert(item6);
STinsert(item7);
STsort(head);
printf(\”\\n\”);
struct Item item11 = STselect(2);
printf(\”%c\\n\”,item11.c);
STdelete(‘i‘);
STsort(head);

}

main(){
test();
}