数据结构题（tree),编译对了就是结果不对，求指教。。。。。
#include <stdio.h>#include <stdlib.h>
#include "string.h"
以下是二叉树建立、插入删除child等的ADT没有错误
typedef struct node
{
void* dataptr;
struct node* left;
struct node* right;
}NODE;
typedef struct
{
int count;
int (*compare)(void* argu1,void* argu2);
NODE* root;
}BST_TREE;
BST_TREE*BST_Create(int(*compare)(void*argu1,void*argu2))
{
BST_TREE* tree;
tree=(BST_TREE*)malloc(sizeof(BST_TREE));
if(tree)
{
tree->root=NULL;
tree->count=0;
tree->compare=compare;
}
return tree;
}
NODE* _insert(BST_TREE*tree,NODE* root,NODE*newptr)
{
if(!root)
return newptr;
if(tree->compare(newptr->dataptr,root->dataptr)<0)
{
root->left=_insert(tree,root->left,newptr);
return root;
}
else
{
root->right=_insert(tree,root->right,newptr);
return root;
}
return root;
}
bool BST_Insert(BST_TREE*tree,void*dataptr)
{
NODE*newptr;
newptr=(NODE*)malloc(sizeof(NODE));
if(!newptr)
return false;
newptr->right=NULL;
newptr->left=NULL;
newptr->dataptr=dataptr;
if(tree->count==0)
tree->root=newptr;
else
_insert(tree,tree->root,newptr);
(tree->count)++;
return true;
}
NODE* _delete(BST_TREE*tree,NODE* root,void* dataptr,bool *success)
{
NODE* dltptr,*exchptr,*newroot;
void* holdptr;
if(!root)
{
*success=false;
return NULL;
}
if(tree->compare(dataptr,root->dataptr)<0)
root->left=_delete(tree,root->left,dataptr,success);
else if( tree->compare(dataptr,root->dataptr)>0)
root->right=_delete(tree,root->right,dataptr,success);
else
{
dltptr=root;
if(!root->left)
{
free(root->dataptr);
newroot=root->right;
free(dltptr);
*success=true;
return newroot;
}
else if(!root->right)
{
newroot=root->left;
free(dltptr);
*success=true;
return newroot;
}
else
{
exchptr=root->left;
while(exchptr->right)
exchptr=exchptr->right;
holdptr=root->dataptr;
root->dataptr=exchptr->dataptr;
exchptr->dataptr=holdptr;
root->left=_delete(tree,root->left,exchptr->dataptr,success);
}
}
return root;
}
bool BST_Delete(BST_TREE* tree,void*dltkey)
{
bool success;
NODE* newroot;
newroot=_delete(tree,tree->root,dltkey,&success);
if(success)
{
tree->root=newroot;
(tree->count)--;
if(tree->count==0)
tree->root=NULL;
}
return success;
}
void* _retrieve(BST_TREE* tree,void*dataptr,NODE* root)
{
if(root)
{
if(tree->compare(dataptr,root->dataptr)<0)
return _retrieve(tree,dataptr,root->left);
else if(tree->compare(dataptr,root->dataptr)>0)
return _retrieve(tree,dataptr,root->right);
else return root->dataptr;
}
else
return NULL;
}
void* BST_Retrieve(BST_TREE* tree,void*keyptr)
{
if(tree->root)
return _retrieve(tree,keyptr,tree->root);
else
return NULL;
}
void _traverse(NODE* root,void(*process)(void*dataptr))
{
if(root)
{
_traverse(root->left,process);
process(root->dataptr);
_traverse(root->right,process);
}
return;
}
void BST_Traverse(BST_TREE *tree,void(*process)(void*dataptr))
{
_traverse(tree->root,process);
return;
}
bool BST_Full(BST_TREE *tree)
{
NODE* newptr=(NODE*)malloc(sizeof(*(tree->root)));
if(newptr)
{
free(newptr);
return false;
}
else
return true;
}
void _destroy(NODE* root)
{
if(root)
{
_destroy(root->left);
free(root->dataptr);
_destroy(root->right);
free(root);
}
return;
}
BST_TREE* BST_Destroy(BST_TREE*tree)
{
if(tree)
_destroy(tree->root);
free(tree);
return NULL;
}
以上无错误
以下是我写的，就是打开某个文件（该文件是通讯录，里边记录了名字和号码），把信息取出来建立树，然后进行一系列操作
typedef struct
{
char* cmpname;//姓
char* name;
char* maze;//存电话号码
}person;
int namecmp(void* name1,void* name2)//按姓的顺序排
{
int result;
if(strcmp(((person*)name1)->cmpname,((person*)name2)->cmpname)<0)
result=-1;
else if(strcmp(((person*)name1)->cmpname,((person*)name2)->cmpname)>0)
result=1;
else result=0;
return result;
}
void buildphonelist(BST_TREE* bstroot)
{
char fileid[20];
FILE* fpin;
printf("input file id\n");
scanf("s",fileid);
//printf("%s",fileid);
fpin=fopen(fileid,"r");
person* relate=(person*)malloc(sizeof(person));
while(fscanf(fpin,"%s",relate->name)!=EOF)
{
fscanf(fpin,"%s",relate->cmpname);
//printf("%s",relate->cmpname);
if(fgets(relate->maze,15,fpin)==NULL)
{
printf("error\n");
exit(100);
}
BST_Insert(bstroot,relate);
relate=NULL;
relate=(person*)malloc(sizeof(person));
}
fclose(fpin);
relate=NULL;
return;
}
void printphonelist(void* phone)
{
printf("%s %s %s\n",((person*)phone)->name,((person*)phone)->cmpname, ((person*)phone)->maze);
return;
}
void filin(void*dataptr)
{
printf("please input the file's name\n");
char filename[20];
scanf("%s",filename);
FILE* flip;
flip=fopen(filename,"w");
if(fprintf(flip,"%s%s%s",((person*)dataptr)->name,((person*)dataptr)->cmpname,((person*)dataptr)->maze)!=0)
printf("add failure\n");
return;
}
int main(int argc, char *argv[])
{
int i;
BST_TREE *bstroot;
bstroot=BST_Create(namecmp);
buildphonelist(bstroot);
BST_Traverse(bstroot,printphonelist);
printf("若要查姓名，请输入1；若要加入新姓名，输入2；删去姓名，输入3；打印号码簿，输入4\n");
scanf("%d",i);
if(i==1)
{
printf("input the name\n");
person* chena=(person*)malloc(sizeof(person));
scanf("%s",chena->name);
scanf("%s",chena->cmpname);
chena=(person*)BST_Retrieve(bstroot,chena);
if(chena!=NULL)
printf("%s %s %s\n",chena->name,chena->cmpname,chena->maze);
else
printf("there is no such man\n");
chena=NULL;
}
if(i==2)
{
printf("input the new name and telephone number\n");
person* addname=(person*)malloc(sizeof(person));
scanf("%s%s%s",addname->name,addname->cmpname,addname->maze);
if(BST_Insert(bstroot,addname))
printf("add name successfully\n") ;
else
printf("fail to add new name\n");
addname=NULL;
}
if(i==3)
{
printf("input the name you want to delete\n");
person* deletename=(person*)malloc(sizeof(person));
scanf("%s%s",deletename->name,deletename->cmpname);
if(BST_Delete(bstroot,deletename))
printf("delete the name successfully\n");
else
printf("fail to delete the name\n");
deletename=NULL;
}
if(i==4)
{
BST_Traverse(bstroot,printphonelist);
}
//写入文件
BST_Traverse(bstroot,filin);
if(BST_Destroy(bstroot)!=NULL)
printf("fail to destroy the tree \n");
system("PAUSE");
return 0;
}
