二叉排序树的建立与删除

周国庆 《二叉排序树的建立与删除》 第16页 共19页

p=t; f=NULL; while(p){

if(p->data==k) break; f=p; if(p->data>k) p=p->lchild; else p=p->rchild;

}

if(p==NULL){ }

printf(\关键字不存在!\\n\return t;

if(p->lchild==NULL){

if(f==NULL)

t=p->rchild;

else if(f->lchild==p)

f->lchild=p->rchild;

else f->rchild=p->rchild; free(p); } else{

q=p; s=p->lchild; while(s->rchild){ } if(q==p)

q->lchild=s->lchild; q=s; s=s->rchild;

周国庆 《二叉排序树的建立与删除》 第17页 共19页

else q->rchild=s->lchild;

p->data=s->data; }

void createbst(bitree *root) //二叉排序树的建立 {

int i,data,cnt;

*root=NULL; //置空树 printf(\请输入数据个数: \ //设置输入数据个数 scanf(\ printf(\请输入数据: \

for(i=0;i

void table() //显示选项列表 {

printf(\ 二叉树操作:\\n\

printf(\ 1. 创建二叉树 \\n\ printf(\ 2. 搜索节点 \\n\ printf(\ 3. 插入节点 \\n\ printf(\ 4. 删除节点 \\n\ printf(\ 0. 退出 \\n\}

}

free(s);

return t;

周国庆 《二叉排序树的建立与删除》 第18页 共19页

int main() {

int data,menu;bitree root;

table(); //调用table函数显示操作列表 printf(\请输入相应操作:\ scanf(\

while(!(menu>=0 && menu<=4)){ //输入序号不存在，操作出错

printf(\操作有问题,请重新输入:\ scanf(\}

while(menu!=0){ //建立循环，选择不同的操作

switch(menu){

case 1:{ //选择操作1，即二叉排序树的创建

printf(\创建二叉树: \\n\ createbst(&root); display(root); printf(\ break; }

case 2:{ //选择操作2，即在二叉排序树中进行查找

printf(\请输入你想搜索的关键字:\ scanf(\ int t=searchbst(root,data); if(t!=INF){

printf(\查找成功: \ printf(\ }

else printf(\关键字不存在\\n\ break; }

周国庆 《二叉排序树的建立与删除》 第19页 共19页

case 3:{ //选择操作3，即在二叉排序树中进行插入操作

printf(\请输入你想插入的关键字:\ scanf(\ insertbst(&root,data); display(root); printf(\ break; }

case 4:{ //选择操作4，即在二叉排序树中进行删除操作

printf(\请输入你想删除的关键字:\ scanf(\ deletebst(root,data); display(root); printf(\ break; } }

printf(\请继续进行相应操作:\ scanf(\ } return 0; }