编译没错，运行时，当插入一个数时，输出时却多了一个负数，（二叉树插入）
编译没错，运行时，当插入一个数时，输出时却多了一个负数，（二叉树插入）求高手指点一下！！！！先谢了~
代码如下：
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define N 10 // 数据元素个数
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
typedef int Status; //用Status代替int 类型
typedef int KeyType; // 设关键字域为整型
typedef struct{
KeyType key; // 关键字域
int others;
} ElemType;
// 数据元素类型定义
typedef ElemType TElemType; // 关键字类型说明
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild; // 结点左右孩子指针
}BiTNode, *BiTree; // 二叉树的二叉链表存储表示，定义一个结点
Status InitDSTable(BiTree *DT) {
*DT=NULL;
return OK;
}
// 操作结果: 构造一个空的动态查找表DT
void DestroyDSTable(BiTree *DT) {
if(*DT) // 判断DT是否是空树
{
if((*DT)->lchild) // 判断结点是否有左孩子
DestroyDSTable(&(*DT)->lchild); // 销毁结点左孩子子树
if((*DT)->rchild) // 判断结点是否有右孩子
DestroyDSTable(&(*DT)->rchild); //销毁结点右孩子子树
free(*DT); // 释放根结点
*DT=NULL; // 空指针赋0
}
}
// 初始条件: 动态查找表DT存在。操作结果: 销毁动态查找表DT
BiTree SearchBST(BiTree T,KeyType key){
if((!T)||EQ(key,T->data.key))
return (T); // 查找结束
else if LT(key,T->data.key) // 在左子树中继续查找
return SearchBST(T->lchild,key);
else
return SearchBST(T->rchild,key); // 在右子树中继续查找
}
// 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，
// 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。
void SearchBST1(BiTree *T,KeyType key,BiTree f,BiTree *p,Status *flag) {
if(!*T) // 查找不成功
{
*p=f;
*flag=FALSE;
}
else if EQ(key,(*T)->data.key) // 查找成功
{
*p=*T;
*flag=TRUE;
}
else if LT(key,(*T)->data.key)
SearchBST1(&(*T)->lchild,key,*T,p,flag); // 在左子树中继续查找
else
SearchBST1(&(*T)->rchild,key,*T,p,flag); // 在右子树中继续查找
}
// 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，否则返回FALSE。
Status InsertBST(BiTree *T, ElemType e){
BiTree p,s;
Status flag;
SearchBST1(T,e.key,NULL,&p,&flag);
if(!flag) // 查找不成功
{
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; // 树中已有关键字相同的结点，不再插入
}
// 从二叉排序树中删除结点p，并重接它的左或右子树。
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->rchild) // 右子树空则只需重接它的左子树（待删结点是叶子也走此分支）
{
q=*p;
*p=(*p)->lchild;
free(q);
}
else if(!(*p)->lchild) // 只需重接它的右子树
{
q=*p;
*p=(*p)->rchild;
free(q);
}
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的左子树
free(s);
}
}
// 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点并返回TRUE；否则返回FALSE。
Status DeleteBST(BiTree *T,KeyType key){
if(!*T) // 不存在关键字等于key的数据元素
return FALSE;
else
{
if EQ(key,(*T)->data.key) // 找到关键字等于key的数据元素
Delete(T);
else if LT(key,(*T)->data.key)
DeleteBST(&(*T)->lchild,key);
else
DeleteBST(&(*T)->rchild,key);
return TRUE;
}
}
// 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数
// 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次
void TraverseDSTable(BiTree DT,void(*Visit)(ElemType e)){
if(DT)
{
TraverseDSTable(DT->lchild,Visit); // 先中序遍历左子树
Visit(DT->data); // 再访问根结点
TraverseDSTable(DT->rchild,Visit); // 最后中序遍历右子树
}
}
void print(ElemType c) //以下主函数调用
{
printf("(%d,%d) ",c.key,c.others);
}
void main() //主函数，用于测试二叉排序树的查找
{
char q;
BiTree dt,p;
int i,select;
KeyType j;
ElemType k;
ElemType r[10]={{45,1},{12,2},{53,3},{3,4},{37,5},{24,6},{100,7},{61,8},{90,9},{70,10}}; // 测试数据
InitDSTable(&dt); // 构造空表
for(i=0;i<10;i++)
InsertBST(&dt,r[i]); // 依次插入数据元素
H1: printf("\n");
printf(" *********** 抽象函数（ADT）：动态查找表的实现 *********** ");
printf("\n\n");
printf(" 实现内容有： 1、遍历原有表\n");
printf(" 2、查找表内值\n");
printf(" 3、删除表内值\n");
printf(" 4、插入一个值\n");
printf(" 5、销毁表\n");
printf(" 6、退出系统\n");
printf("\n");
printf("请选择操作（1~6）：");
scanf("%d",&select);
switch(select)
{
H2: case 1:printf("\n原有的表遍历如下：\n");
TraverseDSTable(dt,print);
printf("\n");
printf("请按“Enter键”返回.....");
getchar(); //从键盘缓冲区清除执行scanf函数后留在缓冲区中的“回车”字符
getchar();
system("cls");
goto H1;
H3: case 2:printf("\n原有的表遍历如下：\n");
TraverseDSTable(dt,print);
printf("\n");
printf("请输入要查找的值：");
scanf("%d",&j);
p=SearchBST(dt,j);
if(p)
{
printf("查找成功：");
printf("(%d,%d)",p->data.key,p->data.others);
getchar();
printf("\n");
printf("是否继续查找？(Y/N):");
q=getchar();
getchar();
if(q=='Y'||q=='y')
goto H3;
else
{
system("cls");
goto H1;
}
}
else
{
printf("\n查找失败，表中无此值，是否继续查找？(Y/N):");
getchar();
q=getchar();
if(q=='Y'||q=='y')
goto H3;
else
{
system("cls");
goto H1;
}
}
H4: case 3:printf("\n原有的表遍历如下：\n");
TraverseDSTable(dt,print);
printf("\n");
printf("请输入要删除的值： ");
scanf("%d",&j);
//getchar();
//q=getchar();
p=SearchBST(dt,j);
if(p)
{
printf("删除此值后：\n");
DeleteBST(&dt,j);
TraverseDSTable(dt,print);
printf("\n是否继续删除？(Y/N):");
getchar();
q=getchar();
if(q=='Y'||q=='y')
goto H4;
else
{
system("cls");
goto H1;
}
}
else
{
printf("\n删除失败，表中无此值，是否继续删除？(Y/N):");
getchar();
q=getchar();
if(q=='Y'||q=='y')
goto H4;
else
{
system("cls");
goto H1;
}
}
H5: case 4:printf("\n原有的表遍历如下：\n");
TraverseDSTable(dt,print);
printf("\n");
printf("请输入要插入的值：");
scanf("%d",&k.key);
p=SearchBST(dt,k.key);
if(!p)
{
printf("插入此值后：\n");
k.others=k.others+(N+1);
InsertBST(&dt,k);
TraverseDSTable(dt,print);
printf("\n");
printf("是否继续插入新值？(Y/N):");
getchar();
q=getchar();
if(q=='Y'||q=='y')
goto H5;
else
{
system("cls");
goto H1;
}
}
else
{
printf("\n插入失败，表中已存在此值，是否继续插入？(Y/N):");
getchar();
q=getchar();
if(q=='Y'||q=='y')
goto H5;
else
{
system("cls");
goto H1;
}
}
case 5:DestroyDSTable(&dt);
printf("动态表销毁成功....");
goto H2;
case 6:system("cls");
printf("\n\n\n\n\n\n\n\n\n ************ 谢谢使用！************");
printf("\n\n\n ");
system("pause");
}
}
