二叉排序树的建立查找插入和删除.doc

数据结构】二叉排序树的建立，查找，插入和删除实践题/*sy53.c*/#include#includetypedefintKeyType;typedefstructnodeKeyTypekey;structnode*lchild,*rchild;BSTNode;typedefBSTNode*BSTree;BSTreeCreateBST(void);voidSearchBST(BSTreeT,KeyTypeKey);voidInsertBST(BSTree*Tptr,KeyTypeKey);voidDelBSTNode(BSTree*Tptr,KeyTypeKey);voidInorderBST(BSTreeT);main()BSTreeT;charch1,ch2;KeyTypeKey;printf(建立一棵二叉排序树的二叉链表存储n);T=CreateBST();ch1=y;while(ch1=y|ch1=Y)printf(请选择下列操作：n);printf(1-更新二叉排序树存储n);printf(2-二叉排序树上的查找n);printf(3-二叉排序树上的插入n);printf(4-二叉排序树上的删除n);printf(5-二叉排序树中序输出n);printf(6-退出n);scanf(n%c,&ch2);switch(ch2)case1:T=CreateBST();break;case2:printf(n请输入要查找的数据：);scanf(n%d,&Key);SearchBST(T,Key);printf(查找操作完毕。n);break;case3:printf(n请输入要插入的数据：);scanf(n%d,&Key);InsertBST(&T,Key);printf(插入操作完毕。n);break;case4:printf(n请输入要删除的数据：);scanf(n%d,&Key);DelBSTNode(&T,Key);printf(删除操作完毕。n);break;case5:InorderBST(T);printf(n二叉排序树输出完毕。n);break;case6:ch1=n;break;default:ch1=n; BSTreeCreateBST(void)BSTreeT;KeyTypeKey;T=NULL;printf(请输入一个关键字(输入0时结束输入)：n);scanf(%d,&Key);while(Key)InsertBST(&T,Key);printf(请输入下一个关键字(输入0时结束输入)：n);scanf(n%d,&Key);returnT;voidSearchBST(BSTreeT,KeyTypeKey)BSTNode*p=T;while(p)if(p-key=Key)printf(已找到n);return;p=(Keykey)?p-lchild:p-rchild;printf(没有找到n);voidInsertBST(BSTree*T,KeyTypeKey)BSTNode*f,*p;p=(*T);while(p)if(p-key=Key)printf(树中已有Key不需插入n);return;f=p;p=(Keykey)?p-lchild:p-rchild;p=(BSTNode*)malloc(sizeof(BSTNode);p-key=Key;p-lchild=p-rchild=NULL;if(*T)=NULL)(*T)=p;elseif(Keykey)f-lchild=p;elsef-rchild=p;/*InsertBST*/voidDelBSTNode(BSTree*T,KeyTypeKey)BSTNode*parent=NULL,*p,*q,*child;p=*T;while(p)if(p-key=Key)break;parent=p;p=(Keykey)?p-lchild:p-rchild;if(!p)printf(没有找到要删除的结点n);return;q=p;if(q-lchild&q-rchild)for(parent=q,p=q-rchild;p-lchild;parent=p,p=p-lchild);child=(p-lchild)?p-lchild:p-rchild;if(!parent)*T=child;elseif(p=parent-lchild)parent-lchild=child;elseparent-rchild=child;if(p!=q)q-key=p-key;fr