二叉排序树的建立遍历查找删除结点.cpp

二叉排序树的建立遍历查找删除结点

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct{
    ElemType key;
}KeyType;   //元素类型
typedef struct node
{KeyType data;
 struct node *lch,*rch;
}Snode,*BiTree;
Snode *creat_bt();
Snode *insertl(Snode *t,Snode *s);
void inorder(Snode *p);
BiTree find(BiTree root,ElemType key);
void Delete(Snode *H,ElemType key);
void main()
{Snode *H;int k;char ch;BiTree s;ElemType key;/*Snode T*/;
 do{printf("\n\n\n");
   printf("\n   1  建立二叉排序树");
   printf("\n   2  中序遍历二叉树并查找给定结点的值是否存在");
   printf("\n   3  删除二叉排序树中的结点");
   printf("\n   4  结束程序运行"  );
   printf("\n===========================");
   printf("\n  请输入你的选择(1,2,3,4):");scanf("%d",&k);
   switch(k)
   {case 1:{H=creat_bt();}break;
    case 2:{printf("\n  中序遍历输出:");
	        inorder(H);
            printf("\n");
            do{    //二叉排序树的查找，可多次查找，并输出查找的结果
            printf("Input the key you want to search:");
            scanf("%4d",&key);
            s=find(H,key);
            if (s!=NULL) printf("success,the value is %4d ",s->data.key);
            else         printf("unsuccess");
            printf("\ncontinue?y:n\n");getchar();
            ch=getchar();
			}while(ch=='y'||ch=='Y');
		   }break;
	case 3:{printf("/n请输入要删除的数据：");
            scanf("%4d",&key);
            Delete(H,key);
            printf("删除操作完毕。/n");}break;
    case 4:{ }break;
   }
}while(k!=4);
printf("\n      再见！       ");scanf("%d",&ch);
}
/*建立二叉排序树*/
Snode *creat_bt()
{Snode *t0,*s;int n,i;KeyType k;
 printf("\n  n=?");scanf("%d",&n);
 t0=NULL;
 for(i=1;i<=n;i++)
 {printf ("\n %d key=?",i);scanf("%d",&k);
  s=(Snode*)malloc(sizeof(Snode));
  s->data=k;s->lch=NULL;s->rch=NULL;
  t0=insertl(t0,s);          /*调用插入函数*/
 }
 return(t0);
}
/*在二叉排序树t中，插入一个结点s的递归算法*/
Snode *insertl(Snode *t,Snode *s)
{if(t==NULL) t=s;
 else if(s->data.key<t->data.key)
 t->lch=insertl(t->lch,s);/*将s插入t的左子树*/
 else t->rch=insertl(t->rch,s);/*将s插入t的右子树*/
 return(t);
}
/*中根遍历二叉树*/
void inorder(Snode *p)
{if(p!=NULL)
{inorder(p->lch);
printf("%8d",p->data);
inorder(p->rch);
}
}
BiTree find(BiTree root,ElemType key){  //在二叉排序树中查找其关键字等于给定值的结点是否存在，并输出相应信息
 Snode *p;
 p=root;
 if (p==NULL) return NULL;
    else if (p->data.key==key) return p;
    else if (key<p->data.key) return find(p->lch,key);
    else return find(p->rch,key);
}
void Delete(Snode *H,ElemType Key)
{Snode *parent=NULL, *p, *q,*child;
p=H;
while(p)
{if(p->data.key==Key) break;
parent=p;
p=(Key<p->data.key)?p->lch:p->rch;
}
if (!p) {printf("没有找到要删除的结点/n");return;}
q=p;
if (q->lch && q->rch)
for (parent=q,p=q->rch; p->lch; parent=p,p=p->lch);
child=(p->lch)?p->lch:p->rch;
if (!parent) H=child;
else {if (p==parent->lch)
parent->lch=child;
else parent->rch=child;
if (p!=q)
q->data.key=p->data.key;
}
free(p);
}