BSTtraverse(left); }
if(fileBST->rightchild!=NULL) {
right=fileBST->rightchild; BSTtraverse(right); } }
UFD *searchBST(UFD *fileBST,char name[30])//在fileBST树中查找名字为name的结点并返回该结点
{ //文件不存在则返回空 int flag;
flag=strcmp(fileBST->name,name); if(flag==0)
return fileBST; //查找成功 else if(flag>0) {
if(fileBST->leftchild==NULL) return NULL; //查找失败 else
searchBST(fileBST->leftchild,name); //递归调用 } else {
if(fileBST->rightchild==NULL) return NULL; else
searchBST(fileBST->rightchild,name); } }
void insertBST(UFD *fileBST,UFD *newBST) //将结点newBST插入原二叉树fileBST中 {
int flag;
flag=strcmp(fileBST->name,newBST->name); if(flag>0) {
if(fileBST->leftchild==NULL) //插入 {
fileBST->leftchild=newBST; newBST->parent=fileBST; } else
insertBST(fileBST->leftchild,newBST); //递归调用
} else {
if(fileBST->rightchild==NULL) //插入 {
fileBST->rightchild=newBST; newBST->parent=fileBST; } else
insertBST(fileBST->rightchild,newBST); //递归调用 }
/*flag=0 的情况已在创建时排除*/ }
UFD *deleteBST(UFD *fileBST,char name[30])//删除名字问name的文件结点 {
UFD *parent_file=NULL,*del_file=NULL; UFD *move_file=NULL,*move_file_parent; del_file=searchBST(fileBST,name); if(del_file==NULL) {
printf(\没有此文件，删除失败！\\n\ getch();
return fileBST; //查找失败 }
if(del_file->file_folder=='o'&&strcmp(del_file->folder->name,\ { printf(\注意，本系统未能实现级联删除，请先逐个删除文件！\ printf(\文件夹非空，删除失败！\\n\ getch();
return fileBST; }
if(del_file->share=='y') //先在共享链中删除 del_in_share(del_file); parent_file=del_file->parent;
if(del_file->leftchild==NULL&&del_file->rightchild==NULL) //被删除结点为子叶结点 {
if(del_file==fileBST) //只有一个结点 {
strcpy(fileBST->name,\ }
else if(parent_file->leftchild==del_file) {
parent_file->leftchild=NULL;
free(del_file); } else { parent_file->rightchild=NULL; free(del_file); } }
else if(del_file->leftchild==NULL||del_file->rightchild==NULL) //被删除结点没有做孩子或右孩子 {
if(del_file->leftchild==NULL) //没有左孩子 { if(parent_file==NULL) //删除的为根结点 { fileBST=del_file->rightchild; del_file->rightchild->parent=NULL; }
else if(parent_file->leftchild==del_file) //右孩子接上 {
parent_file->leftchild=del_file->rightchild; del_file->rightchild->parent=parent_file; }
else //右孩子接上 {
parent_file->rightchild=del_file->rightchild; del_file->rightchild->parent=parent_file; } }
else //没有右孩子 { if(parent_file==NULL) //删除的为根结点 { fileBST=del_file->leftchild; del_file->leftchild->parent=NULL; }
else if(parent_file->leftchild==del_file) //左孩子接上 {
parent_file->leftchild=del_file->leftchild; del_file->leftchild->parent=parent_file; }
else //左孩子接上 {
parent_file->rightchild=del_file->leftchild; del_file->leftchild->parent=parent_file; } }
free(del_file);
}
else //左右孩子都有 {
move_file_parent=del_file->leftchild; move_file=move_file_parent->rightchild;
if(move_file==NULL) //被删除结点的左孩子没有右孩子 {
if(parent_file==NULL) //删除的为根结点 {
fileBST=move_file_parent;
fileBST->rightchild=del_file->rightchild; fileBST->parent=NULL; }
else if(parent_file->leftchild==del_file)
parent_file->leftchild=move_file_parent; else
parent_file->rightchild=move_file_parent; move_file_parent->parent=parent_file;
move_file_parent->rightchild=del_file->rightchild; } else {
while(move_file->rightchild!=NULL) //寻找右边最底下的结点 {
move_file=move_file->rightchild;
move_file_parent=move_file_parent->rightchild; }
move_file_parent->rightchild=NULL; move_file->leftchild=del_file->leftchild; move_file->rightchild=del_file->rightchild; if(move_file->rightchild!=NULL)
move_file->rightchild->parent=move_file; //右孩子的双亲也要改变
move_file->parent=del_file->parent;
if(fileBST==del_file) //删除的为根结点 fileBST=move_file; free(del_file);