二叉排序树Microsoft Word 文档

《二叉排序树Microsoft Word 文档》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#defineENDKEY0typedefstructnode{intkey;structnode*lchild,*rchild;}BSTNode,*BSTree;inttotalsum=0;intbijiaosum=0;intshibaisum=0;voidInsertBST(BSTree*bst,intkey){BSTrees;if(*bst==NULL){s=(BSTree)malloc(sizeof(BSTNode));s->k

2、ey=key;s->lchild=NULL;s->rchild=NULL;*bst=s;}elseif(key<(*bst)->key)InsertBST(&((*bst)->lchild),key);elseif(key>(*bst)->key)InsertBST(&((*bst)->rchild),key);}intkey[20];voidCreateBST(BSTree*bst){statici=0;*bst=NULL;scanf("%d",&key[i]);totalsum++;while(key

3、[i]!=ENDKEY){InsertBST(bst,key[i]);scanf("%d",&key[i]);}}intSearchBST(BSTreebst,intkey){BSTreeq;q=bst;while(q){if(q->key==key)return1;if(q->key>key){q=q->lchild;shibaisum=shibaisum+2;}else{q=q->rchild;shibaisum=shibaisum+2;}bijiaosum++;}return0;}voidPreOr

4、der(BSTreebst){if(bst!=NULL){printf("%d",bst->key);PreOrder(bst->lchild);PreOrder(bst->rchild);}}BSTNode*DelBST(BSTreet,intk){BSTNode*p,*f,*s,*q;p=t;f=NULL;while(p){if(p->key==k)break;f=p;if(p->key>k)p=p->lchild;elsep=p->rchild;}if(p==NULL)returnt;if(p->l

5、child==NULL){if(f==NULL)t=p->rchild;elseif(f->lchild==p)f->lchild=p->rchild;elsef->rchild=p->rchild;free(p);}else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}if(q==p)q->lchild=s->lchild;elseq->rchild=s->lchild;p->key=s->key;free(s);}returnt;}voidmai

6、n(){BSTreebst;intk,i,j;printf("建立二叉排序树，请输入序列:");CreateBST(&bst);printf("先序遍历输出序列为:");PreOrder(bst);printf("");for(i=0;i

7、lsum)*shibaisum);printf("输入插入字");scanf("%d",&k);InsertBST(&bst,k);PreOrder(bst);printf("");printf("输入删除字");scanf("%d",&j);DelBST(bst,j);PreOrder(bst);}