资源描述：
《二叉排序树查找C程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、程序运行截图如下：源程序清单如下：#defineNULL0#defineERROR0#defineOK1#include#includetypedefstructLnode{intkey;structLnode*lchild,*rchild;}BiTnode,*BiTree;/*初始化二叉排序树*/voidInitBiTree(BiTree*t){*t=NULL;}/*判断二叉排序树是否为空*/intEmptyBitree(BiTreet){if(t==NULL){return1;}else{retu
2、rn0;}}/*在二叉排序树中查找值为k的结点，返回指向该结点的指针*/BiTreeSearchBST(BiTreet,intk){BiTreep;p=t;while((p!=NULL)&&(p->key!=k)){if(kkey){p=p->lchild;}else{p=p->rchild;}}return(p);}/*中序遍历二叉排序树，得到升序排列的关键字值*/voidInorderBiTree(BiTreep){if(p){InorderBiTree(p->lchild);printf("%d",p->key);Inord
3、erBiTree(p->rchild);}}/*在二叉排序树中插入关键字k*/voidInsertBST(BiTree*t,intk){BiTnode*f,*p=*t;while(p){if(p->key==k){return;}f=p;p=(kkey)?p->lchild:p->rchild;}p=(BiTree)malloc(sizeof(BiTnode));p->key=k;p->lchild=p->rchild=NULL;if(*t==NULL){*t=p;}elseif(kkey){f->lchild=p;}el
4、se{f->rchild=p;}}/*在二叉排序树中删除关键字值为k的结点*/voidDelBST(BiTree*t,intk){BiTreep,f,q,s,root;root=*t;p=*t;f=NULL;while(p){if(p->key==k){break;/*找到关键字为k的结点*/}f=p;p=(kkey)?p->lchild:p->rchild;/*分别在*p的左、右子树中查找*/}if(!p){return;}if(p->lchild==NULL&&p->rchild==NULL){if(p==*t){*t=NUL
5、L;}elseif(p==f->lchild){f->lchild=NULL;}else{f->rchild=NULL;}free(p);}elseif(p->lchild==NULL&&p->rchild!=NULL){/**p无左子树*/if(f==NULL){*t=p->rchild;}elseif(f->lchild==p){f->lchild=p->rchild;/*将*p的右子树链接到其父结点的左链上*/}else{f->rchild=p->rchild;/*将*p的右子树链接到其父结点的右链上*/}free(p);}else
6、if(p->rchild==NULL&&p->lchild!=NULL){/**p有左子树*/if(f==NULL){*t=p->lchild;}elseif(f->lchild==p){f->lchild=p->lchild;/*用*p的左子树代替*p*/}else{f->rchild=p->lchild;}free(p);}elseif(p->lchild!=NULL&&p->rchild!=NULL){/**p既有左子树又有右子树*/q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}
7、p->key=s->key;if(q!=p){q->rchild=s->lchild;}else{q->lchild=s->lchild;}free(s);}}voidmain(){BiTreet=NULL,p;intkey;InitBiTree(&t);printf("请输入关键字的值，以0结束：");scanf("%d",&key);while(key){InsertBST(&t,key);scanf("%d",&key);}printf("中序遍历建立的二叉排序树的序列为：");InorderBiTree(t);printf("
8、");printf("请输入要删除的结点的关键字的值：");scanf("%d",&key);DelBST(&t,key);printf("删除后的二叉排序树的中序序列为：");Inord
