各位哥哥帮我看看怎么改正
二叉排序树.rar
(4.89 KB)
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"
#define OK 1
#define FALSE 0
#define TRUE 1
typedef int KeyType;
typedef int info;
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
typedef struct
{
KeyType key;
//info otherinfo;
}ElemType; /* 数据元素类型 */
typedef struct BiTNode
{
ElemType data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)
{/* 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找 */
/* 成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上 */
/* 访问的最后一个结点并返回FALSE,指针f指向T的双亲，其初始调用值为NULL */
if(!T) /* 查找不成功 */
{p=f;return 0;}
else if EQ(key,T->data.key)
{p=T;return 1;}
else if LT(key,T->data.key)/* 查找成功 */
SearchBST(T->lchild,key,T,p);/* 在左子树中继续查找 */
else SearchBST(T->rchild,key,T,p);/* 在右子树中继续查找 */
}//SearchBST
Status InsertBST(BiTree &T,ElemType e)
/* 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE， */
{
BiTree s,p;
if(!SearchBST(T,e.key,NULL,p))/* 查找不成功 */
{
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!p) T=s;/* 被插结点*s为新的根结点 */
else if LT(e.key,p->data.key)
p->lchild=s;/* 被插结点*s为左孩子 */
else p->rchild=s;/* 被插结点*s为右孩子 */
return TRUE;
}
else return FALSE; /* 树中已有关键字相同的结点，不再插入 */
}//InsertBST
int Delete(BiTree &p)
/* 从二叉排序树中删除结点p，并重接它的左或右子树。算法9.8 */
{
BiTree q,s;
if(!p->rchild) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支） */
{
q=p;
p=p->lchild;
free(q);
}//if
else if(!p->lchild)/* 只需重接它的右子树 */
{
q=p;
p=p->rchild;
free(q);
}//else if
else/* 左右子树均不空 */
{
q=p;
s=p->lchild;
while(s->rchild)/* 转左，然后向右到尽头（找待删结点的前驱） */
{q=s;
s=s->rchild;
}
p->data=s->data;/* s指向被删结点的＂前驱＂（将被删结点前驱的值取代被删结点的值） */
if(q!=p)
q->rchild=s->lchild; /* 重接*q的右子树 */
else q->lchild=s->lchild;/* 重接*q的左子树 */
delete s;
}//else
return OK;
}//Delete
Status DeleteBST(BiTree &T,KeyType key)
{/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点， */
/* 并返回TRUE；否则返回FALSE。算法9.7 */
if(!T)/* 不存在关键字等于key的数据元素 */
return FALSE;
else
{
if EQ(key,T->data.key) /* 找到关键字等于key的数据元素 */
return Delete(T);
else if LT(key,T->data.key)
return DeleteBST(T->lchild,key);
else return DeleteBST(T->rchild,key);
}//else
}//DeleteBST
int InsertBSTD(BiTree &T)
/* 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE， */
/* 否则返回FALSE。算法9.6(改) */
{
ElemType e;
printf("insert the data,until input -1:\n");
scanf("%d",&e.key );
while(e.key!=-1)
{
InsertBST(T,e);
scanf("%d",&e.key);
}//while
return 1;
}//InsertBSTD
void PrintD(BiTree T)
{
if(T->lchild)PrintD(T->lchild);
printf("->%d",T->data.key);
if(T->rchild)PrintD(T->rchild);
}//PrintD
int DeleteBSTD(BiTree &T)
{
ElemType e;
printf("\ninput the data you want to delete:\n");
scanf("%d",&e.key);
DeleteBST(T,e.key);
return 1;
}//DeleteBSTD
int main()
{
BiTree T;
InsertBSTD(T);
PrintD(T);
DeleteBSTD(T);
PrintD(T);
return OK;
}
这不好吧
