二叉搜索树（BST）的插入和删除C语言

插入

Bintree Insert(int X,Bintree BST) { if(!BST)//若原树为空，生成并返回一个只有一个结点的二叉树一个 { BST=malloc(sizeof(struct Binary));//有问题！！！ BST->Data = X; BST->left=NULL; BST->right=NULL; } else if(X < BST->Data) { BST->left = Insert(X,BST->left);//若改为return Insert(X,BST->left);则类似于查找 } else if(X > BST->Data) { BST->right = Insert(X,BST->right); } return BST; }

删除

Bintree delete(int X,Bintree BST) { Bintree temp; if(BST==NULL) printf("ERROR"); else if(X < BST->Data)//没找到 BST->left = delete (X,BST->left); else if(X > BST->Data)//没找到， BST->right = delete (X,BST->right); else //找到了 { if((BST->left)&&(BST->right)) { temp=Min(BST->right);//右子树的最小值 BST->Data=temp->Data; BST->right= delete(BST->Data,BST->right);//将右子树最小值删掉 } else { temp=BST; if(!BST->left)//有右孩子或者无子节点 { BST=BST->right; } else if(!BST->right)//有左孩子或没有子节点 BST=BST->left; free(temp); } } return BST; }

删除操作中包含的查找最小值函数

typedef Bintree Position; Position Min(Bintree BST) { if(BST==NULL) return NULL; else if(BST->left==NULL) return BST; else return Min(BST->left); }

完整代码

#include<stdio.h> #include<stdlib.h> typedef struct Binary *Bintree; struct Binary{ int Data; Bintree left; Bintree right; }; Bintree Insert(int X,Bintree BST) { if(!BST)//若原树为空，生成并返回一个只有一个结点的二叉树一个 { BST=malloc(sizeof(struct Binary));//有问题！！！ BST->Data = X; BST->left=NULL; BST->right=NULL; } else if(X < BST->Data) { BST->left = Insert(X,BST->left);//若改为return Insert(X,BST->left);则类似于查找 } else if(X > BST->Data) { BST->right = Insert(X,BST->right); } return BST; } typedef Bintree Position; Position Min(Bintree BST) { if(BST==NULL) return NULL; else if(BST->left==NULL) return BST; else return Min(BST->left); } Position Find(int X,Bintree BST) { if(!BST) return NULL; else if(BST->Data<X) return Find(X,BST->right); else if(BST->Data>X) return Find(X,BST->left); else return BST; } Bintree delete(int X,Bintree BST) { Bintree temp; if(BST==NULL) printf("ERROR"); else if(X < BST->Data)//没找到 BST->left = delete (X,BST->left); else if(X > BST->Data)//没找到， BST->right = delete (X,BST->right); else //找到了 { if((BST->left)&&(BST->right)) { temp=Min(BST->right);//右子树的最小值 BST->Data=temp->Data; BST->right= delete(BST->Data,BST->right);//将右子树最小值删掉 } else { temp=BST; if(!BST->left)//有右孩子或者无子节点 { BST=BST->right; } else if(!BST->right)//有左孩子或没有子节点 BST=BST->left; free(temp); } } return BST; }