#include <stdio.h>
#include <stdlib.h>
#include<string.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status是函数的类型，其值是函数结果状态码
typedef int Status;
//ElemType是数据元素类型，暂时定义为int
typedef int ElemType;
//二叉排序树的存储结构
typedef struct BiTNode { // 结点结构
ElemType data;
struct BiTNode *lchild, *rchild; // 左右指针
} BiTNode, *BiTree;
void InsertBST(BiTree *T,int Key)
{BiTNode *f,*p;
p=(*T);
while(p)
{if(p->data==Key)
{printf("树中已有Key不需插入\n");
return;
}
f=p;
p=(Key<p->data)?p->lchild:p->rchild;
}
p=(BiTNode*)malloc(sizeof(BiTNode));
p->data=Key;
p->lchild=p->rchild=NULL;
if ((*T)==NULL) (*T)=p;
else if (Key<f->data) f->lchild=p;
else f->rchild=p;
}/*InsertBST*/
//创建二叉排序树
BiTree CreateBST(void)
{BiTree T;
int Key;
T=NULL;
printf("请输入一个关键字(输入0时结束输入)：\n");
scanf("%d",&Key);
while (Key)
{InsertBST(&T,Key);
scanf("%d",&Key);
}
return T;
}
//查询元素
BiTree SearchBST (BiTree T, int key) { // 算法9.5(a)
// 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，
// 若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
if (key==T->data) return (T); // 查找结束
else if (key<T->data)
return SearchBST(T->lchild, key); // 在左子树中继续查找
else
return SearchBST(T->rchild, key); // 在右子树中继续查找
} // SearchBST
//查询元素,并反回指针
Status SearchBST(BiTree T, int key, BiTree f, BiTree &p) {
// 算法9.5(b)
// 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，
// 若查找成功，则指针p指向该数据元素结点，并返回TRUE，
// 否则指针p指向查找路径上访问的最后一个结点并返回FALSE，
// 指针f指向T的双亲，其初始调用值为NULL
if (!T) { p = f; return FALSE; } // 查找不成功
else if (T->data==key) { p = T; return TRUE; } // 查找成功
else if (key<T->data)
return SearchBST(T->lchild, key, T, p); // 在左子树中继续查找
else
return SearchBST(T->rchild, key, T, p); // 在右子树中继续查找
} // SearchBST
//插入元素
Status InsertBST(BiTree &T, ElemType e) { // 算法9.6
// 当二叉排序树T中不存在关键字等于e.key的数据元素时，
// 插入e并返回TRUE，否则返回FALSE
BiTree p,s;
if (!SearchBST(T, e, NULL, p)) { // 查找不成功
s = (BiTree)malloc(sizeof(BiTNode));
s->data = e; s->lchild = s->rchild = NULL;
if (!p) T = s; // 插入 s 为新的根结点
else if (e<p->data) p->lchild=s; // 插入s为左孩子
else p->rchild = s; // 插入 s 为右孩子
return TRUE;
} else return FALSE; // 树中已有关键字相同的结点，不再插入
} // Insert BST
// 从二叉排序树中删除结点p，并重接它的左或右子树
void DelBSTNode(BiTree *T,int Key)
{ BiTNode *parent=NULL, *p, *q,*child;
p=*T;
while(p)
{if(p->data==Key) break;
parent=p;
p=(Key<p->data)?p->lchild:p->rchild;
}
if (!p) {printf("没有找到要删除的结点/n");return;}
q=p;
if (q->lchild && q->rchild)
for (parent=q,p=q->rchild; p->lchild; parent=p,p=p->lchild);
child=(p->lchild)?p->lchild:p->rchild;
if (!parent) *T=child;
else {if (p==parent->lchild)
parent->lchild=child;
else parent->rchild=child;
if (p!=q)
q->data=p->data;
}
free(p);
}
//遍历
void InorderBST(BiTree T)
{ if(T!=NULL)
{InorderBST(T->lchild);
printf("%5d",T->data);
InorderBST(T->rchild);
}
}
void main()
{
int e,key,p;
BiTree T,r;
printf("建立一棵二叉排序树的二叉链表存储\n");
T=CreateBST();//建立一棵二叉排序树
printf("请输入要查询的元素：");
scanf("%d",&key);
r=SearchBST (T,key); //查询元素
printf("输出要查询的元素:");
printf("%d",r->data);
printf("\n");
printf("请输入要插入的元素：");
scanf("%d",&e);
printf("\n");
InsertBST(T,e); //插入元素
InorderBST(T);
printf("\n");
printf("请输入要删除的元素："); //删除元素
scanf("%d",&p);
DelBSTNode(&T,p);
InorderBST(T);
printf("\n");
}
本回答被网友采纳