原代码例如以下：
#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, Key v){
Key t = key(h->item);
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);
}
//插入子程序
link insertR(link h, Item item){
Key v = key(item), t = key(h->item);
if(h==z)return NEW(item,z,z,1);
if(v<t) h->l = insertR(h->l,item);
else h->r = insertR(h->r,item);
(h->N)++;return h;
}
//插入主程序
link STinsert(Item item){
return insertR(head,item);
}
//删除子程序
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 STdelete(Key v){
deleteRR(head,v);
}
void sortR(link h){
if(h==z)return;
sortR(h->l);
if(h->item.key!=0)
printf("%d ",h->item.key);
sortR(h->r);
}
void STsort(){
sortR(head);
}
void test(){
struct Item item1 = {322,'a'};
struct Item item2 = {23,'a'};
struct Item item3 = {2,'a'};
struct Item item4 = {332,'a'};
STinit();
STinsert(item1);STinsert(item2);
STinsert(item4);STinsert(item3);
STsort();
printf("
");
struct Item item11 = STsearch(23);
printf("%d
",item11.key);
// STdelete(23);
STdelete(322);
STsort();
}
main(){
test();
}
