1利用二叉排序树的插入实现二叉排序树的创建
//1利用二叉排序树的插入实现二叉排序树的创建
//2 分别用递归和非递归的方法实现二叉排序树的查找
//3（选作）尝试实现二叉排序树的删除
#include
#include
#include
typedef int ElemType;
typedef struct node
{
ElemType data;
struct node *lchild ,*rchild;
}BSTNode,*BSTTree;
//二叉排序树的插入（递归算法）
void InsertBSTTree(BSTTree *BST , ElemType key)
{
//如果树为空，则待插入的元素生成的结点为根
if((*BST)==NULL)
{
(*BST)=(BSTNode*)malloc(sizeof(BSTNode));
(*BST)->data=key;
(*BST)->lchild=NULL;
(*BST)->rchild=NULL;
}
else if((*BST)->data>key)//如果待插入的元素比根结点元素值小
InsertBSTTree(&((*BST)->lchild),key);//插入在根结点的左子树
else//否则
InsertBSTTree(&((*BST)->rchild),key);//插入在根结点的右子树上
}
//非递归的方法实现二叉排序树的插入
void InsertBST(BSTTree *bst,ElemType key)
//若在二叉排序树bst中不存在关键字等于key的元素，插入该元素
{
BSTTree s;
if((*bst)==NULL)//递归结束的条件
{
s=(BSTTree)malloc(sizeof(BSTNode));//申请新的结点s
s->data=key;
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}
else
if(keydata)
InsertBST(&((*bst)->lchild),key);//将s插入左子树
else
if(key>(*bst)->data)
InsertBST(&((*bst)->rchild),key);//将s插入右子树
}
//创建一棵二叉排序树
BSTTree CreateBSTTree()
{
BSTTree bst=NULL;
ElemType x;
while(1)
{
//输入数据
scanf("%d",&x);
if(x==-1)break;
InsertBST(&bst,x);
}
return bst;
}
//中序遍历
void InOrder(BSTTree BST)
{
if(BST!=NULL)
{
InOrder(BST->lchild);
printf("%5d",BST->data);
InOrder(BST->rchild);
}
}
BSTTree SearchBST(BSTTree bst,ElemType key)//在根指针bst所指的二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点的指针，否则返回空指针 {
if(!bst) return NULL;
else
if(bst->data==key)
return bst; //查找成功
else
if(bst->data>key)
return SearchBST(bst->lchild,key); //在左子树中继续查找
else
return SearchBST(bst->rchild,key); //在右子树中继续查找
}
BSTTree SearchBST2(BSTTree bst,ElemType key)//在根指针bst所指的二叉排序树中，非递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点的指针，否则返回空指针 {
BSTTree q;
q=bst;
while(q)
{
if(q->data==key)
return q; //查找成功
if(q->data>key) //在左子树中继续查找
q=q->lchild;
else //在右子树中继续查找
q=q->rchild;
}
return NULL;
}
BSTNode * DelBST(BSTTree t, ElemType k) /*在二叉排序树t中删去关键字为k的结点*/ {
BSTNode *p, *f,*s ,*q;
p=t;
f=NULL;
while(p) /*查找关键字为k的待删结点p*/
{
if(p->data==k ) break; /*找到则跳出循环*/
f=p; /*f指向p结点的双亲结点*/
if(p->data>k)
p=p->lchild;
else
p=p->rchild;
}
if(p==NULL) return t; /*若找不到，返回原来的二叉排序树*/
if(p->lchild==NULL) /*p无左子树*/
{
if(f==NULL)
t=p->rchild; /*p是原二叉排序树的根*/
else
if(f->lchild==p) /*p是f的左孩子*/
f->lchild=p->rchild ; /*将p的右子树链到f的左链上*/ else /*p是f的右孩子*/
f->rchild=p->rchild ; /*将p的右子树链到f的右链上*/ free(p); /*释放被删除的结点p*/
}
else /*p有左子树*/
{
q=p;
s=p->lchild;
while(s->rchild) /*在p的左子树中查找最右下结点*/ {
q=s;
s=s->rchild;
}
if(q==p)
q->lchild=s->lchild ; /*将s的左子树链到q上*/ else
q->rchild=s->lchild;
p->data=s->data; /*将s的值赋给p*/
free(s);
}
return t;
} /*DelBST*/
void main()
{
BSTTree BST;
int k;
int m;
BSTTree result;
printf("建立二叉排序树，请输入序列:\n");
BST=CreateBSTTree(); //调用创建函数
printf("中序遍历后输出的该序列为:");
InOrder(BST); //中序遍历这棵树
printf("\n请输入要查找的元素:");
fflush(stdin);
scanf("%d",&k);
result = SearchBST(BST,k); //用递归法查找二叉排序树
result = SearchBST2(BST,k); //用递归法查找二叉排序树
if (result != NULL)
printf("要查找的元素为%d\n",result->data);
else
printf("未找到!\n");
printf("请输入要删除的元素:");
fflush(stdin);
scanf("%d",&m);
result = DelBST(BST,m);
printf("删除该元素后得到的序列为:"); InOrder(result);
printf("\n");
}